[racket] Math library ready for testing

2012/12/11 Martin Neal <marty.neal at gmail.com>:
> First - I love the library.  There's so much functionality that it's going
> to take quite some time to explore it all
>
> I'd love to see an `in-primes` function added to math/number-theory.

Excellent idea. I have added it to the todo-list.

> Using a pseudo prime test (eg. Fermat, Miller-Rabin, etc.) however is not
> ideal when trying to enumerate a large swath of prime numbers starting at 2.
> Here's an example program that tries to sum all the primes under a million
>
> (time
>  (for/sum ([i (in-primes)]
>   #:break (<= 1000000 i))
>    i))
>
> Which takes ~27 seconds on my machine using the current version of prime?
> Using a trial-division version like
> (define (prime2 n)
>   (case n
>     [(-2 2) #t]
>     [(-1 1) #f]
>     [else
>      (and (odd? n)
>  (for/and ([trial-divisor (in-range 3 (+ 1 (integer-sqrt n)) 2)])
>    (positive? (remainder n trial-divisor))))]))
>
> and redefining next-prime to use that, trims the time it takes to sum down
> to 0.25 seconds.
>
> It seems there are two typical use cases for dealing with primes.  The first
> is dealing with big primes for the use of cryto etc. where you're typically
> interested in only 1 prime number at a time.  This is where it makes sense
> to have these complicated primality tests with a low Big-O, and higher
> coefficient.  The other use case is dealing with many smaller primes, where
> having a sieve or trial division makes more sense.

You make an excellent point. The performance of prime? needs to
be improved for small primes.

Currently prime? works as follows:

For a small (less than 10000)  number n  prime? looks up primality of
with a simple (vector-ref small-primes n).

For a large number (greater than 10000) a pseudo prime test is used.

Originally the limit for small primes was a million, but that limit is too
large for a general purpose library.

The first change will be to replace the vector with a bit-vector
in order to store larger table without using too much space.

The second will be to experiment with "medium numbers"
and see whether trial division is faster than the pseudo
prime test, when the small prime limit is raised to larger number
again.

Here is how I plan to use bit-vectors:

  To test whether a small number n is prime,
   step one is to check whether it is divisible
   by 2, 3 or 5. If not then if the number is small
   then its primality is looked up in a bit-vector.

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?

-- 
Jens Axel Søgaard