rapido - tablas de multiplicar

¿Cómo multiplicar números de terabytes?

Question

Al multiplicar números muy grandes, se utiliza la multiplicación basada en FFT (consulte el algoritmo de Schönhage-Strassen ). Por razones de rendimiento, estoy guardando en caché los factores de twiddle. El problema es que para grandes números (tamaño Gigabyte) necesito tablas FFT de tamaño 2 ^ 30 y más, que ocupan demasiada RAM (16 GB y más). Así que parece que debería usar otro algoritmo.

Existe un software llamado y-cruncher, que se utiliza para calcular Pi y otras constantes, que pueden multiplicar números de tamaño terabyte. Utiliza un algoritmo llamado NTT híbrido y otro algoritmo llamado VST (consulte A Peak en y-cruncher v0.6.1 en la sección El algoritmo de multiplicación de VST ).

¿Alguien puede arrojar algo de luz sobre estos algoritmos o cualquier otro algoritmo que pueda usarse para multiplicar números de tamaño terabyte ?

Answer 1

FFT se puede hacer en la misma matriz con un número constante de memoria adicional (puede que sea necesario intercambiar el número de manera inteligente). Por lo tanto, también se puede hacer en el disco duro. En el peor de los casos es un registro (N) * N veces de acceso al disco. Parece mucho más lento que hacerlo en RAM, pero la complejidad general sigue siendo la misma.