Path: utzoo!dptcdc!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!DACTH51.BITNET!FM
From: FM@DACTH51.BITNET
Newsgroups: comp.lang.scheme
Subject: Re: Oaklisp bignum multiplication
Message-ID: <8904181811.AA02341@BLOOM-BEACON.MIT.EDU>
Date: 18 Apr 89 18:58:00 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Organization: The Internet
Lines: 24

In my original posting I asked about Oaklisp's multiplication  method.  Barak
Pearlmutter answered:

    "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."

Just how big ?  I evaluated various multiplication methods  once,  and  found
that numbers have to be bigger than ~1000 decimal digits to gain  from  using
Karatsubas method.  Such large numbers don't occur  very  often,  even  in  a
computational algebra system.

    "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."

Sure, but computing factorials isn't terrible  exiting.  And  my  feeling  is
that in applications like computational algebra systems it will happen  quite
often that one of the operands will be rather small.

! Martin Schoenert, martins@rwthinf.uucp, fm@datch51.bitnet, +49 241 804551 !
! Lehrstuhl D Mathematik, RWTH, Templergraben 64, D 51 Aachen, West Germany !