jueves, septiembre 04, 2008

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

2 comentarios:

Anónimo dijo...

Coñe, vaya bicharraco...

Aitor Iriarte dijo...

Jeje, bueno, ahora mismo está un poco caótico, con variables del mismo tipo declaradas en líneas diferentes, variables que se utilizan para lo mismo y les he dado diferentes nombres, argumentos que se pasan con valor cuando van a ir mejor por referencia,...

Pero bueno, en cuanto he visto que funciona lo he publicado, y es que llevaba mucho retraso.

Hay un par de cosas que tengo que explicar.

1-La forma de almacenar en los string los números y por lo tanto, la forma en la que muestra el resultado.

2-La forma en la que calculo el cuadrado de los números que creo que es optimizable.