home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17088 < prev    next >
Encoding:
Internet Message Format  |  1992-12-17  |  2.0 KB
  1. Path: sparky!uunet!pipex!warwick!uknet!acorn!armltd!dseal
  2. From: dseal@armltd.co.uk (David Seal)
  3. Newsgroups: sci.math
  4. Subject: Re: Factor 69 digit integer
  5. Message-ID: <10917@armltd.uucp>
  6. Date: 16 Dec 92 17:52:11 GMT
  7. References: <1gb5bkINNm71@roundup.crhc.uiuc.edu>
  8. Sender: dseal@armltd.uucp
  9. Distribution: sci
  10. Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK
  11. Lines: 38
  12.  
  13. In article <1gb5bkINNm71@roundup.crhc.uiuc.edu> hougen@focus.csl.uiuc.edu
  14. (Darrell Roy Hougen) writes:
  15.  
  16. >[attributions removed, since they were wrong]
  17. >>>> Please help me.  I need the prime factors of 
  18. >>>>  132686104398972053177608575506090561429353935989033525802891469459697
  19. >
  20. >Write your own infinite precision arithmetic program to solve the
  21. >problem.  Here's a start:
  22. >(1) Store each number in an array, e.g., A[1..69] where each element
  23. >of the array is a digit, ie., 0,1,...,9.
  24. >(2) Implement a divide and carry algorithm.  For each remainder,
  25. >you'll have to try all dividends from 0 through 9 up the first that
  26. >doesn't work.
  27.  
  28. Shouldn't you have put a large number of smileys after this? People might
  29. take it seriously...
  30.  
  31. (For those who did:
  32.   (a) implementing infinite precision arithmetic in *decimal* is distinctly
  33.       unusual, not to say inefficient - a base like 2^16 or 2^32 would make
  34.       more sense;
  35.   (b) calculating a quotient digit by trying possibilities from 0 upwards
  36.       until one doesn't work is highly inefficient, especially for
  37.       reasonably large bases - binary chop would be better, some methods
  38.       using the result of single precision divisions described in Knuth yet
  39.       better;
  40.   (c) if you've drawn the conclusion that you can then solve the problem by
  41.       trial division, think again - if this number is at all difficult to
  42.       factorise, you could run trial division on current hardware for the
  43.       current age of the universe and still not have made any real inroads
  44.       on the problem. Fortunately, there *are* better algorithms.
  45. )
  46.  
  47. David Seal
  48. dseal@armltd.co.uk
  49.  
  50. All opinions are mine only...
  51.