Quería saber cómo se implementan BigInt y otras cosas similares. Traté de verificar el código fuente de JAVA, pero era todo griego y latino para mí. ¿Puede explicarme el algo en palabras? No hay código, por lo que entiendo lo que estoy usando cuando uso algo de la API de JAVA. saludos¿Cómo funcionan las implementaciones de BigNums?
Conceptualmente, de la misma manera que usted hace arbitrariamente el tamaño arithmentic a mano. Tiene algo así como una matriz de valores y algoritmos para las diversas operaciones que funcionan en la matriz.
Supongamos que quiere agregar 100 a 901. Se empieza con los dos números como matrices:
[0, 1, 0, 0]
[0, 9, 0, 1]
Cuando se agrega, el algoritmo de adición se inicia desde la derecha, toma 0+1, dando 1, 0+0, dando 0, y - ahora la parte difícil - 9+1 da 10, pero ahora tenemos que llevarlo, por lo que agregamos 1 a la siguiente columna y ponemos (9+1)%10 en la tercera columna.
Cuando sus números crecen lo suficiente - más que 9999 en este ejemplo - entonces tiene que asignar más espacio de alguna manera.
Esto es, por supuesto, algo simplificado si almacena los números en orden inversa.
Las implementaciones reales usan palabras completas, por lo que el módulo es realmente una gran potencia de dos, pero el concepto es el mismo.
Hay una muy buena sección sobre esto en Knuth.
muchas gracias :) – shahensha
También hay una sección en Recetas Numéricas (que sigue a Knuth de cerca). La parte difícil es obtener la multiplicación correcta. El algoritmo de la escuela no se escala muy bien, por lo que utiliza trucos (por ejemplo, FFT). Una vez que tenga la multiplicación, puede expresar muchas cosas con ella. –