home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10586 < prev    next >
Encoding:
Text File  |  1992-08-25  |  1.8 KB  |  37 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: Primes
  5. Message-ID: <1992Aug25.224828.123034@Cookie.secapl.com>
  6. Date: Tue, 25 Aug 1992 22:48:28 GMT
  7. References: <9208171021.aa01492@Paris.ics.uci.edu> <1992Aug18.091619.10152@waikato.ac.nz> <1992Aug22.040442.17832@mailer.cc.fsu.edu>
  8. Organization: Security APL, Inc.
  9. Lines: 26
  10.  
  11. In article <1992Aug22.040442.17832@mailer.cc.fsu.edu> rose@fsu1.cc.fsu.edu writes:
  12. >In article <1992Aug18.091619.10152@waikato.ac.nz>, bill@waikato.ac.nz writes...
  13. >>Does anyone know how Mathematica stores its table of primes, and how efficient
  14. >>it is in terms of space and access time? What's the minimum space a table
  15. >>of primes can be compressed into if constant access time to find the nth prime
  16. >>is required?
  17. >> 
  18. >In general, one can use a bitmap to represent a prime number table.  Some
  19. >compression can be obtained by representing only odd numbers, or only 
  20. >odd numbers not divisible by 3.  
  21. >Then the computer can count primes by using the count bits function of the 
  22. >hardware amazingly fast.  If the computer does not have a count bits 
  23. >function, then this technique is lost.
  24.  
  25. No, it isn't.  Software bit-counting, using a table lookup method, is also
  26. very fast.  You can't do it directly in most higher-level languages,
  27. however, without giving up a lot of the speed.
  28.  
  29. However, this does not answer the original question, which required constant
  30. access time to find the nth prime.  This can be provided by including a list
  31. of the (n*k)th primes for some (fairly large) k.
  32.  
  33. This method, like just listing the primes, requires O(n) space to store the
  34. primes (with or without the auxilliary table).  The difference is the
  35. constant.  I doubt you can do better than this maintaining O(1) access time
  36. for the nth prime; with O(log n) time it might be possible.
  37.