fast arithmetic with little extra memory

[Paul Zimmermann]

       Hi,

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.

See http://portal.acm.org/citation.cfm?id=1576743

Paul Zimmermann