home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3429 < prev    next >
Encoding:
Text File  |  1993-01-07  |  2.0 KB  |  44 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!pipex!harlqn.co.uk!harlqn!markt
  3. From: markt@harlqn.co.uk (Mark Tillotson)
  4. Subject: Re: Arbitrary precision with large bases
  5. In-Reply-To: emcoop@bnr.ca's message of Wed, 6 Jan 1993 14:45:19 GMT
  6. Message-ID: <MARKT.93Jan7124834@wundt.harlqn.co.uk>
  7. Lines: 31
  8. Sender: news@harlqn.co.uk (Usenet News Account)
  9. Organization: Harlequin Limited, Cambridge, England
  10. References: <martin.726311424@bert> <1icne6INNpjb@uwm.edu> <21495.1993Jan6.094519@bcars148>
  11. Date: Thu, 7 Jan 1993 12:48:34 GMT
  12.  
  13. emcoop@bnr.ca (hume smith) writes:
  14. > not quite true - see aho/hopcroft/ullman.  f1*f2 can be done
  15. > in O(n log(n)) where n=max(log(f1), log(f2)).  there's a rather large
  16. > constant involved though... it may be better to implement the two
  17. > and find out empirically when to switch methods.
  18. > 
  19. Not _quite_ right, the complexity of Schoenhase-Strassen(?) multiply
  20. algorithm is O(N.log(N).log(log(N))).  It must count as one of the 10
  21. neatest algorithms I know!  You do need to implement both methods,
  22. because for really large N, it has to recurse to do the
  23. sub-multiplications (this recursion is responsible for the log(log(N))
  24. term).  When the numbers are small enough (each level of recursion
  25. deals with numbers which have a number of digits roughly the
  26. square-root of the number of digits in the higher level), you switch
  27. to long-multiplication.
  28.  
  29. I believe a tight implementation can start to win over straight long
  30. division when the numbers get to be a few hundred digits long.   When
  31. the numbers get to be hundreds of millions of digits, it is the only
  32. practical way!!
  33.  
  34. I believe there is a proof that no multiplication method can be better
  35. than O(N.log(log(N))) or some such.
  36.  
  37.  
  38. ------------------------------------------------------
  39. |\  /|          | ,  M. Tillotson       Harlequin Ltd. \
  40. | \/ |  /\| |/\ |<   markt@uk.co.harlqn  Barrington Hall,\
  41. |    |  \_| |   | \  +44 223 872522       Barrington,      \
  42. I came, I saw, I core-dumped...            Cambridge CB2 5RG \
  43.  
  44.