Fast multiplication of large numbers

The usual method of multiplying two numbers is proportional to the product MN of the number of digits in the two numbers. The Fast Fourier Transform can be used to do this in time N log N for two numbers with N digits. This is explained in volume II of Knuth's The art of computer programming.

There are a small number of programs available which do this, but they vary a lot in performance. Probably the fastest is one written by George Woltman (on compuserve) in assembly language for Pentium CPU's exclusively. The best known is probably the package mp of Fortran routines distributed by by David H. Bailey (send a message with help on the subject line to mp-reqst@nas.nasa.gov).

I have written two versions myself, prompted to some extent by Joe Buhler, one for generic UNIX machines and a variant using some SPARC assembly language modules. I will probably make my programs available eventually. In the meantime, you might want to read some notes I have written, mostly to guide myself in this project.