home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3430 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.1 KB
  1. Path: sparky!uunet!usc!howland.reston.ans.net!sol.ctr.columbia.edu!ira.uka.de!Sirius.dfn.de!urmel.informatik.rwth-aachen.de!martin
  2. From: martin@math.rwth-aachen.de (  Martin Schoenert)
  3. Newsgroups: comp.programming
  4. Subject: Re: Arbitrary precision with large bases
  5. Date: 7 Jan 93 14:25:38 GMT
  6. Organization: Rechnerbetrieb Informatik - RWTH Aachen
  7. Lines: 30
  8. Message-ID: <martin.726416738@bert>
  9. References: <martin.726311424@bert> <1icne6INNpjb@uwm.edu> <21495.1993Jan6.094519@bcars148>
  10. NNTP-Posting-Host: bert.math.rwth-aachen.de
  11.  
  12. emcoop@bnr.ca (hume smith) writes:
  13.  
  14.     In <martin.726311424@bert>, martin@math.rwth-aachen.de (  Martin Schoenert) said:
  15.     > a)  the larger the base the fewer digits any given integer has in this
  16.     >     base.  Since (for example) the performance of the multiplication
  17.     >     is proportional to the product of the number of digits of the
  18.     >     operands it is always a win to use larger bases (though the win
  19.     >     with base 2^32 over base 10^9 is only about 12.5%).
  20.  
  21.     not quite true - see aho/hopcroft/ullman.  f1*f2 can be done
  22.     in O(n log(n)) where n=max(log(f1), log(f2)).  there's a rather large
  23.     constant involved though... it may be better to implement the two
  24.     and find out empirically when to switch methods.
  25.  
  26. Well yes, but it is not so simple.  Those fancier algorithms also have to
  27. multiply digits (just not so many).  That means that base 2^32 is still
  28. going to win over base 10^10 (just not so much).  Also you need quite
  29. large integer before the fancier methods are faster than the elementary
  30. algorithm.  For example the one with the smallest overhead is Karatsuba's
  31. trick.  With my large integer arithmetic running on an R3000, integers
  32. must have about 200 decimal digits before one Karatsuba splitting pays,
  33. and they must have about 2000 decimal digits before multiplication with
  34. Karatsuba's trick is twice as fast as the elementary algorithm.  For
  35. fourier transform the break-even point is even higher.
  36.  
  37. Martin.
  38.  
  39. -- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
  40. Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
  41. Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany
  42.