Understanding Schönhage-Strassen algorithm (huge integer multiplication)

Question

Hi, I need to multiply several 1000s digits long integers as efficiently as possible in Python. The numbers are read from a file.

I am trying to implement the Schönhage-Strassen algorithm for integer multiplication, but I am stuck on understanding the definition and mathematics behind it, specially the Fast Fourier Transform.

Any help to understand this algorithm, like a practical example or some pseudo-code would be highly appreciated.

Answer 1

1000 digits is "small" for Schönhage-Strassen to be really worth using. You may have a look at the Toom Cook multiplication. gmpy is a Python wrapper to gmp providing these functions.

Answer 2

Chapter 4.3.3 of Knuth's TAOCP describes it and also has some FFT pseudocode in other chapters that could be used for this.