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