10
Necesito multiplicar varios enteros largos de 1000s de la manera más eficiente posible en Python. Los números se leen de un archivo.Entender el algoritmo de Schönhage-Strassen (multiplicación de enteros grandes)
Estoy tratando de implementar el algoritmo Schönhage-Strassen para la multiplicación de enteros, pero estoy atascado en la comprensión de la definición y las matemáticas detrás de ella, especialmente la Transformada rápida de Fourier.
Cualquier ayuda para comprender este algoritmo, como un ejemplo práctico o algún pseudocódigo sería muy apreciado.
Una sugerencia muy importante: no intente implementar su propia FFT a menos que realmente tenga que hacerlo. Si está disponible para python, intente utilizar el FFTW para su cálculo. Será muy superior a cualquier cosa con la que puedas soñar alguna vez. Una simple FFT no es tan difícil, pero la parte más difícil es hacerlo rápido, especialmente si los números que estás crujiendo no son poderes de poderes de dos. – LiKao
@LiKao: Schönhage-Strassen se implementa normalmente utilizando un vector de tamaño fijo de enteros de tamaño arbitrario y la Transformación teórica numérica, mientras que las FFT implementadas por paquetes como FFTW utilizan elementos de coma flotante y de tamaño fijo, por lo que no son realmente muy útil. –