fast arithmetic with little extra memory

Paul Zimmermann Paul.Zimmermann at
Wed Oct 14 22:04:22 CEST 2009


Daniel S. Roche has designed a clever variant of Karatsuba's algorithm
which requires only O(log n) extra memory (in addition to the read-only
n+n input and to the read/write 2n output). Previous best known results
were 2n extra memory (as implemented in GMP) and n extra memory (from
Emmanuel Thomé). He also gives an FFT algorithm with O(1) extra memory.


Paul Zimmermann

More information about the gmp-devel mailing list