[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Oaklisp bignum multiplication
In my original posting I asked about Oaklisp's multiplication method. Barak
"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, email@example.com, firstname.lastname@example.org, +49 241 804551 !
! Lehrstuhl D Mathematik, RWTH, Templergraben 64, D 51 Aachen, West Germany !