[racket] Math library ready for testing

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<http://pre.racket-lang.org/docs/html/math/number-theory.html>`
function added to
math/number-theory<http://pre.racket-lang.org/docs/html/math/number-theory.html>.
 Currently, I've come up with 3 easy ways of generating a sequence of
primes all with varying degrees of performance.

;;method 1 - Bad performance, but I could see someone trying to define
(sequence-map nth-prime (in-naturals))

;;method 2 - Good performance, but still seems wasteful
(sequence-filter prime? (in-naturals))

;;method 3 - Good performance, but clunky to have to define yourself
(define (in-primes [start 2])
(make-do-sequence
   (thunk
    (values
     values
     next-prime
     (next-prime (- start 1))
     #f
     #f
     #f))))

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.

Again, awesome library
Marty

On Sun, Dec 9, 2012 at 3:52 AM, Jens Axel Søgaard <jensaxel at soegaard.net>wrote:

> 2012/12/8 Danny Yoo <dyoo at hashcollision.org>:
> >> Or maybe using a : or something to separate rows for 2D arrays?
> >> (array 1 2 : 3 4)
>
> The matrix library uses arrays to represent the matrices.
> An 2x3 matrix can be constructed as:
>
>    (matrix/dim 2 3
>                        1 2 3
>                        4 5 6)
>
>    (list->matrix '[[1 2 3] [4 5 6]])
>
>   (for/matrix: : Number 2 3 ([i (in-naturals)]) i)
>
> These expressions will all return the same 2D array.
>
> Given that the shape of a matrix is fixed, the problems
> with square parentheses in constructor notation disappear.
> That is, one could let  matrix  be a macro, and it could
> accept both kinds of parentheses:
>
>       (matrix [[1 2 3] [4 5 6]])
>       (matrix ((1 2 3) (4 5 6)))
>
> See more matrix examples here:
>
> https://github.com/plt/racket/blob/master/collects/math/tests/matrix-tests.rkt
>
> --
> Jens Axel Søgaard
>
> ____________________
>   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/20121210/4dc701d8/attachment-0001.html>