[Nickle]New multiply code

Keith Packard keithp@keithp.com
Wed, 18 Apr 2001 00:38:34 -0700


I finally implemented Karatsuba multiplies for large natural product
computations.  This reduces the order of the computation from O(N^2)
to O(N^(log(3)/log(2)), but increases some internal costs and so
is only efficient for larger numbers.

The result has been to improve the benchmark numbers so that the 
numeric-computation limited results are now less than two times slower 
than the equivalent gmp code.  Most of the speedup in the existing 
benchmarks is actually from printing numbers faster.

Perhaps I'll investigate Toom-Cook multiplies later, but Karatsuba is
likely better than Toom-Cook up to several thousand bits which should do
for much of what Nickle is used for today.

-keith