javascript algorithm biginteger integer-division

javascript - ¿Cómo implementar la división Bigint(rápida)?



bigint javascript (3)

La referencia estándar para la aritmética de enteros grandes es el libro Arte de la programación de computadoras de Donald Knuth, Volumen 2, Sección 4.3. Su algoritmo de división es básicamente el algoritmo de la escuela primaria, con algunas pequeñas mejoras.

Por cierto, la mayoría de las personas que implementan aritmética de enteros grandes utilizan una potencia de dos en lugar de una potencia de diez como la raíz de su sistema numérico.

Actualmente estoy haciendo mi propia clase BigInt, dividiendo números por 7 dígitos. (es decir, en base 10,000,000)

Implementé suma, resta y multiplicación, y ahora estoy implementando división y mod. Escribí un código que realiza la división por división larga (estimando números dividiendo los dígitos más significativos), y funciona.

Sin embargo, es demasiado lento. Cuando pruebo operaciones en un número de 108 dígitos y un número de 67 dígitos, se tarda 1.9 ms en calcular la división, mucho más lento que en otras operaciones (0.007 ~ 0.008ms para calcular la suma / resta, 0.1ms para calcular la multiplicación).

Al igual que el algoritmo de Karatsuba y FFT para la multiplicación rápida, ¿qué algoritmo existe para calcular la división? Wikipedia muestra algunos algoritmos de división (que calcula el inverso multiplicativo del divisor y lo multiplica con el dividendo), pero creo que eso no me ayuda mucho a implementar la división. También leo las secciones ''Métodos de enteros grandes'' pero eso tampoco me ayuda ... :(

Le sugiero que eche un vistazo al código fuente de la biblioteca GMP y a las funcionalidades que necesita para JavaScript, o tenga una idea de cómo se hace.

Si hay un buen algoritmo, es probable que esta biblioteca lo tenga; y se distribuye bajo la licencia LGPL.