[racket] Math library ready for testing

FWIW, I think these questions are best answered with an app in hand,
but my apriori guess would be to say that 32k isn't too bad, but that
it also doesn't seem necessary in this case. Martin Neal's micro
benchmark already saw lots of improvements with just a different
algorithm so perhaps that's enough?

Robby

On Tue, Dec 11, 2012 at 5:01 AM, Jens Axel Søgaard
<jensaxel at soegaard.net> wrote:
> 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
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users