Path: utzoo!dptcdc!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!cs!Barak.Pearlmutter
From: Barak.Pearlmutter@cs
Newsgroups: comp.lang.scheme.c
Subject: Re: Oaklisp bignum multiplication
Message-ID: <Mon.Apr.17.16:47:49.1989.bap@F.GP.CS.CMU.EDU>
Date: 17 Apr 89 20:47:00 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Distribution: inet
Organization: The Internet
Lines: 9

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.