miércoles, agosto 27, 2008

Primos gigantes. Fase I




Siguiendo el planning indicado en el post "Como cazar un primo gigante", lo primero es conseguir un número de Maresnne grande.

El número de Maresnne se definía como Mn = 2^n -1 (ver post anterior).

¿Para que n el número es suficientemente grande? Bueno, pues depende. En el año 1952 el número M521 era muy grande, ya que constituyó el número primo más grande conocido hasta entonces.

M521 es un número de 157 dígitos y se logró con una máquina SWAC.

He hecho una pequeña aproximación al programa que nos va a permitir obtener ese primo gigante. Como es lógico el problema es la limitación de los tipos de datos predefinidos tanto en Visual Basic como en el framework.

Poniendo tipos enteros el programa funciona bien hasta el Mersenne 30:

Como se ve los números crecen rápidamente:

M15=32.767.
M20=1.048.575.
M25=33.554.431.
M30=1.073.741.823
Con M31 salta el error SYSTEM.OVERFLOWEXCEPTION: La operación aritmética ha provocado un desbordamiento.

El tipo integer es un entero de 4 bytes (32 bits) con signo por lo que puede variar entre -2.147.483.648 y 2.147.483.647.
Por eso falla el M31.

Luego he decidido utilizar los enteros más grandes:

El tipo long consiste en 8 bytes (64 bits) con signo. Por lo tanto sus valores puede variar entre -9.223.372.036.854.775.808 y 9.223.372.036.854.775.807.
El tipo long de visual basic es totalmente equivalente al tipo System.Int64 del framework .NET.

Bueno, con el tipo long se consigue llegar correctamente al M62 que es igual a 4.611.686.018.427.387.903.

Pero mejor que el tipo long es utilizar el tipo SYSTEM.DECIMAL ya que es el mayor tipo predefinido que podemos utilizar. Utiliza 16 bytes (128 bits) que son una animalada.

Los límites en los que nos movemos son (lo he copiado de la ayuda del .NET):

79.228.162.514.264.337.593.543.950.335 sin separador decimal
0 a +/-7,9228162514264337593543950335 con 28 posiciones a la derecha del signo decimal; el número más pequeño distinto de cero es
+/-0,0000000000000000000000000001 (+/-1E-28).

Con este último tipo de dato gigante llegamos correctamente a M95.
En la imagen vemos el resultado:


El programa Visual Basic.NET utilizado es el siguiente:



Module Module1
Function exponenciacionBinaria(ByVal numero As Integer) As System.Decimal
If numero = 1 Then Return 2
If numero Mod 2 = 0 Then Return exponenciacionBinaria(numero / 2) * exponenciacionBinaria(numero / 2)
Return 2 * exponenciacionBinaria(numero - 1)
End Function
Sub Main()
Dim n As Integer
Dim numeroMersenne As String
Dim dosElevadoAn As System.Decimal
Console.WriteLine("Los números de Mersenne se representan como Mn")
Console.Write("Introduzca el valor de n que quiere calcular: ")
n = Console.ReadLine()
dosElevadoAn = exponenciacionBinaria(n)
numeroMersenne = dosElevadoAn - 1
Console.WriteLine("M" & n & " es igual a " & numeroMersenne)
Console.ReadLine()
End Sub
End Module

6 comentarios:

Anónimo dijo...

Has visto que han encontrado ya el número primo de Mersenne número 45? debe tener ya los 10 millones de dígitos, como aún no ha sido demosrado no han puesto a que M pertenece, lo encontraron el pasado 23 de agosto y según dicen puede tardar 2 semanas en ser verificado, curioso :P

http://www.mersenne.org/prime.htm

Saludos!

Aitor Iriarte dijo...

¡Coño!
Que interesante...No conocía la página de primos mersenne.

¿Has visto lo que ocurrió con el anterior primo descubierto?

"However, the new prime falls short of the 10 million digits required for GIMPS to claim the Electronic Frontier Foundation $100,000 award".

¡Hay un premio para el primo mersenne con 10 millones de dígitos!

A ver si con un poco de suerte este tampoco cumple :-)

Mira, también hay un enlace a un mersenneWiki

Anónimo dijo...

jeje, sí, hay un montón de premios para el que encuentre el primo más grande... a partir de 10, 100, y 1000 millones de dígitos hay varios premios, pero GIMP es un sistema tipo "SETI" (ya sabes el que busca extraterrestres) pero para buscar primos, de manera que imagina contra qué cantidad de ordenadores compites :) para comprobar el último número descubierto hicieron falta 15 ordenadores de 1,5 Ghz trabajando durante 6 días... digamos que, no quiero desanimarte, pero necesitas más máquina...

Por cierto, qué máquina tienes?, otra cosa muy sencilla que podrías añadir al programa es que se pudiese dividir en threads y dar "affinidad" a cada uno, así, si tienes más de un procesador (dual core, quad core... ) irá mucho más rápido, lo digo, porque lancé el programa en un quad core y no mejoraba casi nada ya que hace el salto de procesador a procesador pero nunca de manera simultanea (lógico) de manera que con un dual core sólo aprovechas la mitad de su capacidad de proceso y con un quad el 25%... es el mismo principio que utilizan en GIMP, distribuir trabajo...

Saludos!

Aitor Iriarte dijo...

Ok, incorporaremos Multi-threading.

El problema es que en el nivel de mersenne en el que estamos (n= 95) el programa termina inmediatamente.

En cuanto se almacenen los números en un string tendrán la posibilidad de ocupar hasta 2.000 millones (2^31) de caracteres por lo que realmente podremos ver la mejoría.

En casa no tengo máquinas potentes pero tranquilo que conseguiremos un servidor decente ;-)

Saludos.

Anónimo dijo...

wow... un número que ocupe dos gigas... qué locura :)

Me puse a bajar el número de 9 megas, pero me aburrí, no quiero ni pensar como puede llegar a ser la comprobación de un número de 2.000.000.000 de dígitos... creo que con el sistema computacional actual no lo podremos llegar a ver nunca :)

Aitor Iriarte dijo...

Pero, ¿como que no?
En la web del otro día hay un epílogo que habla de predicciones.

Han hecho un gráfico y calculan que en el año 2024 se podrá llegar a un primo con 1.000.000.000 dígitos.

Espero que lo veamos.

Saludos.