home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3422 < prev    next >
Encoding:
Text File  |  1993-01-06  |  1.4 KB  |  31 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!wupost!uwm.edu!rpi!gatech!swrinde!cs.utexas.edu!torn!nott!bnrgate!bcars267!news
  3. From: emcoop@bnr.ca (hume smith)
  4. Subject: Re: Re: Arbitrary precision with large bases
  5. Message-ID: <21495.1993Jan6.094519@bcars148>
  6. Sender: news@bnr.ca (usenet)
  7. Nntp-Posting-Host: bcars148
  8. Organization: Bell-Northern Research, Ottawa, Canada
  9. X-Poster: Emacs-NNTP-0.1
  10. References: <martin.726311424@bert> <1icne6INNpjb@uwm.edu>
  11. Date: Wed, 6 Jan 1993 14:45:19 GMT
  12. Lines: 17
  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. Hume Smith                      Wenn ich des Tages nicht dreimal
  27. hume.smith@acadiau.ca           mein Schaelchen Coffee trinken darf,
  28. emcoop@bnr.ca              //   so werd' ich ju zu meiner Qual
  29.                          \X/    wie ein verdorrtes Ziegenbraetchen.
  30.  
  31.