Eureka

Por fin he podido cantar eureka. Hoy 4-9-2008 a las 16:32 mientras veía un programa que creo que se llama "Pasalo".

Después de unas cuantas películas y series vistas mientras programaba he podido terminar el programita que calcula los númerso de Mersenne. Todo gracias a los anuncios :-)

Ha tenido su complicación y todavía no está garantizado que funcione en el 100% de los casos. El problema es que pequeños errores no se notan con números de Mersenne pequeños y el programa puede estar mal y dar un montón de resultados buenos. Algún errorcillo ha ocasionado que fallara un número relativamente pequeño como es M20, aunque no fallaban los grandes como M67.

Es un ejercicio interesantísimo ejecutar paso a paso las instrucciones viendo los valores que van tomando las variables. El algoritmo es bastante elegante.

En la imagen de arriba tenemos el flujo del algoritmo para el número de Mersenne 13. Esto es, para n=13. Recomiendo seguirlo para entenderlo.

Se han probado correctamente los números siguientes:

M1=1, M2=3, M3=7, M5=31, M11=2047, M15=32.767, M20=1.048.575, M67=147.573.952.589.676.412.927, M75=37.778.931.862.957.161.709.567.

De todas formas, hay que mantenerlo en cuarentena hasta que consiga los 95 primeros números en un fichero y los compare con los del programa anterior.

Module Module1
    Function exponenciacionBinaria(ByVal numero() As Char) As Char()
        If (numero(0) = "1" And numero(1) = "f") Or numero(0) = Nothing Then
            numero(0) = "2"
            numero(1) = "f"
            Return numero
        End If

        If numero(0) = "0" Or numero(0) = "2" Or numero(0) = "4" Or _
            numero(0) = "6" Or numero(0) = "8" Then
            numero = dividirEntreDos(numero)
            numero = exponenciacionBinaria(numero)
            numero = multiplicarPorSiMismo(numero)
            Return numero
        End If

        Return multiplicarPorDos(exponenciacionBinaria(restarUno(numero)))
    End Function

    Function multiplicarPorSiMismo(ByVal n As Char()) As Char()
        If n(0) = "f" Then
            Return "f"
        End If
        Dim resultadoParcial(n.Length + 2, n.Length + 100) As Char
        Dim resultadoParcialNumerico(n.Length + 2, n.Length + 100) As Integer
        Dim resultadoFinal(n.Length + 100) As Char
        Dim resultadoFinalNumerico(n.Length + 100) As Integer
        Dim contadorColumnasNumeroArriba As Integer = 0
        Dim contadorColumnasNumeroAbajo As Integer = 0
        Dim contadorColumnasResultados As Integer = 0
        Dim llevada = 0
        Dim contador As Integer
        Dim contadorFilasResultados As Integer

        Dim maxDigitos As Integer = 0
        Dim longitudN, longitudResultadoParcial As Integer
        longitudN = 0
        While n(longitudN) <> "f"
            longitudN += 1
        End While

        contadorColumnasNumeroAbajo = 0
        For contadorFilasResultados = 0 To longitudN - 1
            contadorColumnasResultados = 0
            contadorColumnasNumeroArriba = 0
            longitudResultadoParcial = longitudN
            For contador = 1 To contadorFilasResultados
                resultadoParcialNumerico(contadorFilasResultados, contadorColumnasResultados) = 0
                resultadoParcial(contadorFilasResultados, contadorColumnasResultados) = "0"
                contadorColumnasResultados += 1
                longitudResultadoParcial += 1
            Next contador
            Do
                resultadoParcialNumerico(contadorFilasResultados, contadorColumnasResultados) = Val(n(contadorColumnasNumeroAbajo)) * Val(n(contadorColumnasNumeroArriba)) + llevada
                llevada = Int(Val(resultadoParcialNumerico(contadorFilasResultados, contadorColumnasResultados)) / 10)
                resultadoParcial(contadorFilasResultados, contadorColumnasResultados) = (Val(resultadoParcialNumerico(contadorFilasResultados, contadorColumnasResultados)) Mod 10).ToString
                contadorColumnasResultados += 1
                contadorColumnasNumeroArriba += 1
            Loop Until n(contadorColumnasNumeroArriba) = "f"
            If llevada > 0 Then
                contador = contadorColumnasResultados
                While Val(resultadoParcial(contadorFilasResultados, contador)) = 9
                    resultadoParcial(contadorFilasResultados, contador) = "0"
                    contador -= 1
                End While
                longitudResultadoParcial = contador + 1
                resultadoParcial(contadorFilasResultados, contador) = (Val(resultadoParcial(contadorFilasResultados, contador)) + llevada).ToString
                llevada = 0
            End If
            resultadoParcial(contadorFilasResultados, longitudResultadoParcial) = "f"

            If longitudResultadoParcial > maxDigitos Then
                maxDigitos = longitudResultadoParcial
            End If
            contadorColumnasNumeroAbajo += 1
        Next contadorFilasResultados

        Dim cuentaDigitos As Integer
        For contador = 0 To longitudN - 1
            cuentaDigitos = 0
            While resultadoParcial(contador, cuentaDigitos) <> "f"
                cuentaDigitos += 1
            End While
            While cuentaDigitos < maxDigitos
                resultadoParcial(contador, cuentaDigitos) = "0"
                cuentaDigitos += 1
            End While
            resultadoParcial(contador, cuentaDigitos) = "f"
        Next contador

        llevada = 0
        Dim i As Integer
        For contador = 0 To maxDigitos - 1
            For i = 0 To contadorFilasResultados - 1
                If i = 0 Then
                    resultadoFinalNumerico(contador) = Val(resultadoFinalNumerico(contador)) + Val(resultadoParcial(i, contador)) + llevada
                Else
                    resultadoFinalNumerico(contador) = Val(resultadoFinalNumerico(contador)) + Val(resultadoParcial(i, contador))
                End If
                llevada = Int(Val(resultadoFinalNumerico(contador)) / 10)
                resultadoFinal(contador) = Val(resultadoFinalNumerico(contador) Mod 10).ToString
            Next i
        Next contador
        If llevada > 0 Then
            If resultadoFinal(contador) = "9" Then
                resultadoFinal(contador) = "0"
                resultadoFinal(contador + 1) = "1"
                resultadoFinal(contador + 2) = "f"
            Else
                resultadoFinal(contador) = (Val(resultadoFinal(contador)) + llevada).ToString
                resultadoFinal(contador + 1) = "f"
            End If
        Else
            resultadoFinal(maxDigitos) = "f"
        End If
        Return resultadoFinal
    End Function

    Function restarUno(ByVal numeroArestar() As Char) As Char()
        If Val(numeroArestar(0)) > 0 Then
            numeroArestar(0) = (Val(numeroArestar(0)) - 1).ToString
        Else
            Dim i As Integer = 0
            Do
                numeroArestar(i) = "9"
                i += 1
            Loop Until Val(numeroArestar(i)) > 0
            numeroArestar(i) = (Val(numeroArestar(i)) - 1).ToString
        End If
        If numeroArestar(0) = "0" And numeroArestar(1) = "f" Then
            numeroArestar = "f"
        End If
        Return numeroArestar
    End Function

    Function dividirEntreDos(ByVal numero() As Char) As Char()
        Dim longitud As Integer = 0
        Dim temporal() As Char
        Dim dividendoActual As Integer = 0
        Dim resultado As String = ""
        Dim resto As Integer
        Dim indiceActual As Integer = 0
        Dim divisionParcialHecha As Boolean
        Dim i As Integer

        While numero(longitud) <> "f"
            longitud += 1
        End While

        Do
            divisionParcialHecha = False
            dividendoActual = resto * 10 + Val(numero(longitud - 1 - indiceActual))
            Do
                If dividendoActual <> 1 Then
                    resultado = resultado & (Int(dividendoActual / 2)).ToString
                    resto = dividendoActual Mod 2
                    divisionParcialHecha = True
                Else
                    If longitud - indiceActual > 1 Then
                        dividendoActual = 10 + Val(numero(longitud - 2 - indiceActual))
                    Else
                        resultado = resultado & "0"
                        resto = dividendoActual Mod 2
                        divisionParcialHecha = True
                    End If
                End If
                indiceActual = indiceActual + 1
            Loop Until divisionParcialHecha
        Loop Until indiceActual = longitud
        temporal = resultado.ToCharArray
        longitud = temporal.Length
        For i = 0 To longitud - 1
            numero(i) = temporal(longitud - 1 - i)
        Next i
        numero(longitud) = "f"
        Return numero
    End Function

    Function multiplicarPorDos(ByVal n() As Char) As Char()
        If n(0) = "f" Then
            Return "f"
        End If
        Dim resultado(n.Length) As Char
        Dim resultadoParcial As Integer
        Dim contador As Integer = 0
        Dim llevada = 0
        Do
            resultadoParcial = Val(n(contador)) * 2 + llevada
            llevada = Int(resultadoParcial / 10)
            resultado(contador) = (resultadoParcial Mod 10).ToString
            contador += 1
        Loop Until n(contador) = "f"
        If llevada > 0 Then
            resultado(contador) = llevada.ToString
            contador += 1
        End If
        resultado(contador) = "f"
        Return resultado
    End Function

    Sub Main()
        Dim n() As Char
        Dim numeroMersenne As String
        Dim dosElevadoAn As String
        Console.WriteLine("Los números de Mersenne se representan como Mn")
        Console.Write("Introduzca el valor de n que quiere calcular: ")
        n = Console.ReadLine()
        Dim nAlreves(n.Length) As Char
        For i As Integer = 0 To n.Length - 1
            nAlreves(n.Length - 1 - i) = n(i)
        Next i
        nAlreves(n.Length) = "f"
        dosElevadoAn = exponenciacionBinaria(nAlreves)
        numeroMersenne = restarUno(dosElevadoAn)
        Console.WriteLine("M" & n & " es igual a " & numeroMersenne)
        Console.ReadLine()
    End Sub
End Module