<div>First - I love the library. There's so much functionality that it's going to take quite some time to explore it all</div><div><br></div>I'd love to see an `<a href="http://pre.racket-lang.org/docs/html/math/number-theory.html" style="text-decoration:none;color:blue;font-family:monospace;font-size:medium;white-space:nowrap;background-color:rgb(232,232,255)" target="_blank">in-primes</a>` function added to <a href="http://pre.racket-lang.org/docs/html/math/number-theory.html" style="text-decoration:none;color:blue;font-family:serif;font-size:medium;background-color:rgb(245,245,220)" target="_blank"><span style="font-family:monospace;white-space:inherit;color:rgb(38,38,128)">math/number-theory</span></a>. Currently, I've come up with 3 easy ways of generating a sequence of primes all with varying degrees of performance.<div>
<br></div><div>;;method 1 - Bad performance, but I could see someone trying to define </div><div>(sequence-map nth-prime (in-naturals))</div><div><br></div><div><div>;;method 2 - Good performance, but still seems wasteful</div>
<div>(sequence-filter prime? (in-naturals))</div></div><div><br></div><div>;;method 3 - Good performance, but clunky to have to define yourself</div><div>(define (in-primes [start 2])</div><div><div>(make-do-sequence</div>
<div> (thunk</div><div> (values</div>
<div> values</div><div> next-prime</div><div> (next-prime (- start 1))</div><div> #f</div><div> #f</div><div> #f))))</div><div><br></div><div>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</div>
<div><div><br></div><div>(time </div><div> (for/sum ([i (in-primes)]</div><div><span class="Apple-tab-span" style="white-space:pre">        </span> #:break (<= 1000000 i))</div><div> i))</div></div><div><br></div><div>Which takes ~27 seconds on my machine using the current version of prime? Using a trial-division version like</div>
<div><div>(define (prime2 n)</div><div> (case n</div><div> [(-2 2) #t]</div><div> [(-1 1) #f]</div><div> [else </div><div> (and (odd? n)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span> (for/and ([trial-divisor (in-range 3 (+ 1 (integer-sqrt n)) 2)])</div>
<div><span class="Apple-tab-span" style="white-space:pre">        </span> (positive? (remainder n trial-divisor))))]))</div></div><div><br></div><div>and redefining next-prime to use that, trims the time it takes to sum down to 0.25 seconds.</div>
<div><br></div><div>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.</div>
<div><br></div><div>Again, awesome library</div><div>Marty</div><br><div class="gmail_quote">
On Sun, Dec 9, 2012 at 3:52 AM, Jens Axel Søgaard <span dir="ltr"><<a href="mailto:jensaxel@soegaard.net" target="_blank">jensaxel@soegaard.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2012/12/8 Danny Yoo <<a href="mailto:dyoo@hashcollision.org" target="_blank">dyoo@hashcollision.org</a>>:<br>
<div>>> Or maybe using a : or something to separate rows for 2D arrays?<br>
>> (array 1 2 : 3 4)<br>
<br>
</div>The matrix library uses arrays to represent the matrices.<br>
An 2x3 matrix can be constructed as:<br>
<br>
(matrix/dim 2 3<br>
1 2 3<br>
4 5 6)<br>
<br>
(list->matrix '[[1 2 3] [4 5 6]])<br>
<br>
(for/matrix: : Number 2 3 ([i (in-naturals)]) i)<br>
<br>
These expressions will all return the same 2D array.<br>
<br>
Given that the shape of a matrix is fixed, the problems<br>
with square parentheses in constructor notation disappear.<br>
That is, one could let matrix be a macro, and it could<br>
accept both kinds of parentheses:<br>
<br>
(matrix [[1 2 3] [4 5 6]])<br>
(matrix ((1 2 3) (4 5 6)))<br>
<br>
See more matrix examples here:<br>
<a href="https://github.com/plt/racket/blob/master/collects/math/tests/matrix-tests.rkt" target="_blank">https://github.com/plt/racket/blob/master/collects/math/tests/matrix-tests.rkt</a><br>
<span><font color="#888888"><br>
--<br>
Jens Axel Søgaard<br>
</font></span><div><div><br>
____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
</div></div></blockquote></div><br></div>