[racket] Math library ready for testing

On Dec 11, 2012, at 9:03 AM, Jens Axel Søgaard wrote:

> 2012/12/11 Stephen Bloch <bloch at adelphi.edu>:
> 
>> Would it perhaps make more sense for small-primes to contain primes
>> themselves, in increasing order so one can be found by binary search, rather
>> than booleans?  The O(1) behavior would be replaced by O(log(limit)), but
>> perhaps you would save enough memory to put the limit higher.
> 
> I think there are too many primes.
> 
> Since
> 
>> (require math)
>> (nth-prime 78498)
>    1000003
> 
> there are 78497 primes below a million. On a 64 bit machine
> that requires  8*78497 = 627976 bytes.

If you treated it as a vector whose elements were (compile-time-typed) 32-bit ints, that would cut it by a factor of 2, but it would still be a third of a megabyte.  OTOH, a vector of bit-packed booleans would take an eighth of a megabyte for the same limit, and give you faster lookups.  So you're right; my suggestion is probably not a win.

How many primes are below ten million?  A hundred million?  At some point storing the primes will take less memory than storing primality flags, but that point may be above the size of tables we can realistically store today.

Wait: it's conceivable that there is no such crossing point.  As the numbers get big, it takes O(log(limit)) bits to store numbers less than limit.  The number of primes less than limit is Theta(limit/log(limit)), so storing them all takes Theta(limit) space, asymptotically the same as storing the flags.




Stephen Bloch
sbloch at adelphi.edu