Cálculos con números de más de 300 dígitos

Tal vez en alguna ocasión hayas leído que los cálculos del número Pi han llegado hasta aproximaciones de varios miles de dígitos decimales, y tal vez hayas intentado calcularlos. Sin embargo los tipos de datos primitivos como el float en Java ó el Double en .NET, con rangos de números flotantes que pueden tener un rango de unos 300 dígitos decimales, sin embargo, como números flotantes que son, se pierde precisión.

¿Cómo resolver entonces una multiplicación ó suma que implique más de 300 dígitos?. Veamos en este Post un método sencillo pero muy interesante para realizar éste cálculo.

El cálculo de Pi y otros números irracionales como e (y de otros muchos números) tienen complicaciones debido a la cantidad de decimales. Incluso si el número es un entero, por ejemplo quieres multiplicar un número muy muy grande, digamos cantidades de átomos o moléculas o cualquier otra cosa.

Digamos que queremos multiplicar un número de 50 dígitos por otro de 70 dígitos. Dado que no “caben” en los tipos de datos primitivos de ningún lenguaje de programación tendremos que inventarnos un método para realizarlo, esto es, “enseñar” a la computadora a multiplicar de manera un poco diferente a la que realiza. El ejemplo está en pseudocódigo y al final el código en VB.NET, aunque el pseudocódigo es bastante claro y podría ser convertido fácilmente a Java aunque por falta de tiempo en esta ocasión solo lo dejaré en VB.NET y otros (se aceptan colaboraciones).

Las premisas de las que partimos son:
1) que los números con los cuales vamos a operar están almacenados en variables de tipo cadena (String).
2) Que iremos sumando dígito a dígito, para ello tomaremos el dígito, lo convertiremos a número utilizando funciones de conversión de String a Integer (o similar)

La manera tradicional de sumar se explica en las siguientes imágenes.

En la primera imagen (658+231=889) podemos ver que los dígitos se van sumando uno a uno comenzando por el menos significativo (las unidades) y en el esquema está bastante claro el orden y las sumas en cada paso para conformar el resultado final.


En la segunda imagen (769+35=804) podemos ver que:
1) necesitamos que los números tengan igual longitud, y la menos complicada de explicar me pareció que es la de añadir ceros al inicio de la cadena que sea más corta de manera que las dos cadenas (que contienen los dígitos) tengan la misma longitud.

2) Como parte del proceso podemos ver que cuando la suma de los dígitos correspondientes es mayor que 10, entonces tomaremos solo el último dígito resultante, y activamos una “bandera” (señal, variable) de que “llevamos” 1. Ejemplo 9 + 5 = 14, tomamos el 4 y lo escribimos como resultado pero… “llevamos” 1, éste número que “llevamos” (o que “acarreamos”) lo sumaremos con el digito siguiente en la suma (ver imagen 2).

El ejercicio se trata entonces, de ejecutar la serie de pasos anterior tantas veces como dígitos haya e ir guardando el resultado en una variable de tipo cadena.

Un pseudocódigo de acuerdo a lo que podemos ver en las imágenes sería algo como esto (click en la imagen para ver más grande):



Al pseudocódigo anterior le hace falta algo… ¿qué pasa si al sumar los dígitos más significativos resulta que tenemos un número mayor que 10?, ¿Cómo nos damos cuenta o qué condición le ponemos al programa para decirle que en ese caso sí escriba el número completo a la cadena de resultado?. Se me ocurren dos soluciones, una involucra poner un IF y su condición, y la otra es más sencilla…. se trata simplemente de añadir un 0 al inicio de cada cadena una vez que ambas son de la misma longitud (esto se haría en el lugar donde está el “COMENTARIO XYZ”). De esa manera, el acarreo podrá llevarse a cabo si lo hubiera y se sumaría Acarreo + 0 + 0 = Acarreo que sería igual a 1.

A Continuación pueden ver el código en VB.NET. En el código los números no son de 300 dígitos, sin embargo los invito a escribir 200 dígitos o más y probar el algoritmo.


Sub Main()
Dim S1, S2 As String
Dim L1, L2 As Integer
Dim Carry As Byte
Dim Resultado As String = ""

S1 = "98234187364192784619278461923487619237846"
S2 = "2837498749284798791872310928370139812"

L1 = S1.Length
L2 = S2.Length

If L1 <> L2 Then
If L1 > L2 Then
S2 = (New String("0"c, L1 - L2)) + S2
Else
S1 = (New String("0"c, L2 - L1)) + S1
End If
End If

S1 = "0" + S1
S2 = "0" + S2
Carry = 0

Dim D1, D2, D3 As Integer
Dim R1 As String = ""
For i As Integer = S1.Length - 1 To 0 Step -1
D1 = Byte.Parse(S1.Chars(i))
D2 = Byte.Parse(S2.Chars(i))
D3 = Carry + D1 + D2

If D3 >= 10 Then
D3 = D3 - 10
Carry = 1
End If

R1 = D3.ToString
Resultado = R1 + Resultado
Next

MsgBox("El resultado es: " + Resultado)

End Sub


El código presentado aquí puede ser refinado muchísimas veces de manera que sea más eficiente y tenga mejor rendimiento y por lo tanto, consuma menos recursos o ejecute en un tiempo menor. En primer lugar podríamos (y deberíamos) utilizar Arrays en lugar de Strings pero eso ya les queda a ustedes de tarea. Sin embargo, este un buen comienzo y se pone en práctica la lógica de programación. Lo que quería dejarles en este artículo es indicarles que no deben verse limitados por las capacidades de los tipos de datos, siempre hay trucos que se pueden realizar para obtener lo que necesitamos.