[comp.lang.scheme.c] Oaklisp bignum multiplication

Barak.Pearlmutter@cs (04/18/89)

Actually, Sun3 benchmarks came out in favor of the elementary school
algorithm for numbers below a certain size, so the fancy algorithm
doesn't kick in unless both numbers are pretty big.  In any case, you're
correct that things are O( n^.59 m ) where n<m, but by either writing a
balanced factorial function or making a special kind of factor-number
which delays computation until the result is needed and then does a
balanced multiplication tree, (FACT 1000) can be sped up considerably.

						--Barak & Kevin.