[racket] Math library ready for testing

2012/12/11 Pierpaolo Bernardi <olopierpa at gmail.com>:
> On Tue, Dec 11, 2012 at 12:01 PM, Jens Axel Søgaard
> <jensaxel at soegaard.net> wrote:
>
>> Below 60 there are only 16 numbers not divisible by 2, 3 or 5.
>> The number of bytes needed to store primality results for the
>> first million numbers will therefore be
>>       1000000 * 16/60 * 1/8  ~ 33333.3
>>
>> How much space would be reasonable to use in the library?
>
> Would make sense to have a user-tuneable parameter (with a small
> default) for this?
> So a prime intensive computation could do (precompute-primes-up-to
> (expt 10 9) ).

That would make sense.

> What do Mathematica, Maple, etc, do in this case?

Here is what Maxima does (line 628 and below):

https://github.com/andrejv/maxima/blob/master/src/ifactor.lisp

They keep a table of the primes below 10000. Small numbers
are simply looked up in the table.

Medium numbers are divided into ranges. In each range
Miller-Rabin is used with pre-selected moduli. This makes
the test deterministic.

For large numbers a pseudo test is used.

--
Jens Axel Søgaard