Cómo implementar división larga para números enormes (bignums)

Question

Estoy tratando de implementar la división larga para bignums. No puedo usar una biblioteca como GMP desafortunadamente debido a las limitaciones de la programación integrada. Además, quiero el ejercicio intelectual de aprender cómo implementarlo. Hasta ahora, he agregado y multiplicado utilizando matrices de bytes de cualquier longitud (por lo que cada byte es como un dígito base-256).

Estoy tratando de comenzar a implementar la división/módulo y quiero saber por dónde empezar? He encontrado muchos códigos altamente optimizados (también ilegibles) en la red, lo que no me ayuda, y he encontrado muchos libros técnicos matemáticos altamente técnicos de los que no puedo cerrar la brecha entre la teoría y la implementación. .

Si alguien pudiera recomendar un algoritmo popular, y apuntarme a una explicación fácil de entender que se incline hacia la implmenentación, sería fantástico.

-edit: Necesito algoritmos que funcionan cuando el dividendo es ~ 4000bits, y el divisor es de ~ 2000bits

-Editar: ¿Funcionará este algoritmo con la base-256? http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-edit: ¿Este es el algoritmo (división newton) que realmente debería estar usando? http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

Answer 1

Si quieres aprender, comienza con el método de lápiz y papel que usaste en la escuela primaria. Lo creas o no, ese es esencialmente el mismo algoritmo O (n^2) que se usa en la mayoría de las bibliotecas bignum para los números que están en el rango que estás buscando. El primer paso difícil se llama "estimación del cociente", y probablemente sea el más difícil de entender. Una vez que entiendas eso, el resto debería ser fácil.

Una buena referencia es Knuth's "Seminumerical Algorithms". Él tiene muchas discusiones sobre diferentes maneras de hacer la estimación del cociente tanto en el texto como en los ejercicios. Ese libro tiene capítulos dedicados a las implementaciones de bignum.

Answer 2

Esta pregunta tiene más de 2 años, pero para estos números de tamaño, puede consultar el código fuente de OpenSSL. Tiene RSA con números de este tamaño, por lo que tiene muchas rutinas matemáticas optimizadas para números de 1000 a 4000 bits.

Answer 3

¿Está utilizando el vacío Four1 (double double [], int, int) en su código y luego convolviendo y luego haciendo una transformación inversa? Tengo multiplicación para trabajar pero cuando traté de hacer la división de la misma manera que escupió sale un resultado y luego abandono, así que no puedo evitarlo, pero si tiene el tomo llamado "Recetas numéricas en C++", vaya al final y encontrará lo que busca en realidad comienza en la página 916 a 926.