FM@DACTH51.BITNET (04/19/89)
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 !