home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3435 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.6 KB
  1. Xref: sparky comp.programming:3434 comp.programming:3435
  2. Newsgroups: comp.programming,comp.programming
  3. Path: sparky!uunet!utcsri!skule.ecf!torn!nott!bnrgate!bcars267!news
  4. From: emcoop@bnr.ca (hume smith)
  5. Subject: Re: Re: Arbitrary precision with large bases
  6. Message-ID: <21495.1993Jan7.112925@bcars148>
  7. Lines: 48
  8. Sender: news@bnr.ca (usenet)
  9. Nntp-Posting-Host: bcars148
  10. Organization: Bell-Northern Research, Ottawa, Canada
  11. X-Poster: Emacs-NNTP-0.1
  12. References: <martin.726416738@bert> <MARKT.93Jan7124834@wundt.harlqn.co.uk> <martin.726311424@bert> <1icne6INNpjb@uwm.edu> <21495.1993Jan6.094519@bcars148>
  13. Date: Thu, 7 Jan 1993 16:29:25 GMT
  14.  
  15. In <martin.726416738@bert>, martin@math.rwth-aachen.de (  Martin Schoenert) said:
  16. > emcoop@bnr.ca (hume smith) writes:
  17. > 
  18. >     not quite true - see aho/hopcroft/ullman.  f1*f2 can be done
  19. >     in O(n log(n)) where n=max(log(f1), log(f2)).  there's a rather large
  20. >     constant involved though... it may be better to implement the two
  21. >     and find out empirically when to switch methods.
  22. > 
  23. > Well yes, but it is not so simple.  Those fancier algorithms also have to
  24. > multiply digits (just not so many).  That means that base 2^32 is still
  25. > going to win over base 10^10 (just not so much).
  26.  
  27. i don't understand what you mean - AH&U describe their algorithm working
  28. bitwise, but i saw no particular tie to base 2.  i've done it in Emacs Lisp
  29. using base 10000, only because it was easy to print... it should work
  30. in 2^whatever makes your hardware happy.
  31.  
  32. (i also should say that i took some liberty with the O statement i made
  33. over AH&U's; if someone finds that the "obvious" generalisation doesn't
  34. fit my guess...)
  35.  
  36. >  Also you need quite
  37. > large integer before the fancier methods are faster than the elementary
  38. > algorithm.
  39.  
  40. i grant that.  it's up to the implementor whether to bother with a more
  41. complex method for his own uses.  if you're thinking about general usage
  42. though, like a Lisp bignum package, the extra work may be appreciated.
  43.  
  44. In <MARKT.93Jan7124834@wundt.harlqn.co.uk>, markt@harlqn.co.uk (Mark Tillotson) said:
  45. > I believe a tight implementation can start to win over straight long
  46. > division when the numbers get to be a few hundred digits long.   When
  47.   --------
  48. > the numbers get to be hundreds of millions of digits, it is the only
  49. > practical way!!
  50.  
  51. (i hope he meant multiplication, not division)
  52. --
  53. Hume Smith                      Wenn ich des Tages nicht dreimal
  54. hume.smith@acadiau.ca           mein Schaelchen Coffee trinken darf,
  55. emcoop@bnr.ca              //   so werd' ich ju zu meiner Qual
  56.                          \X/    wie ein verdorrtes Ziegenbraetchen.
  57.  
  58.