[racket] Math library ready for testing

I can't type. The correct count of primes less than a million is 78498. And
there is something wrong if (nth-prime 78498) returns 100003, as the
78498th prime is 999983.

On Tue, Dec 11, 2012 at 10:46 AM, Martin Neal <marty.neal at gmail.com> wrote:

> I clicked the link, and the result shows 78498 which jives with nth-prime
>
>
> On Tue, Dec 11, 2012 at 8:31 AM, Phil Bewig <pbewig at gmail.com> wrote:
>
>> There must be an error in the prime-counting function. According to <a
>> href="
>> http://www.wolframalpha.com/input/?i=how+many+primes+less+than+a+million">Wolfram|Alpha</a>,
>> there are 79486 primes less than a million, not 78497.
>>
>> I don't use Racket, but I do have lots of Scheme code that computes with
>> prime numbers at my <a href="http://programmingpraxis.com>blog</a> that
>> you may find useful.
>>
>> On Tue, Dec 11, 2012 at 10:11 AM, Stephen Bloch <sbloch at adelphi.edu>wrote:
>>
>>>
>>> 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
>>>
>>>
>>> ____________________
>>>   Racket Users list:
>>>   http://lists.racket-lang.org/users
>>>
>>
>>
>> ____________________
>>   Racket Users list:
>>   http://lists.racket-lang.org/users
>>
>>
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20121211/703335fd/attachment-0001.html>