New math.erato library: sieve of Eratosthene

diff --git a/extra/math/erato/authors.txt b/extra/math/erato/authors.txt
new file mode 100644 (file)
index 0000000..f3b0233
--- /dev/null
+++ b/extra/math/erato/authors.txt
@@ -0,0 +1 @@
+Samuel Tardieu

diff --git a/extra/math/erato/erato-docs.factor b/extra/math/erato/erato-docs.factor
new file mode 100644 (file)
index 0000000..e5dc82d
--- /dev/null
+++ b/extra/math/erato/erato-docs.factor
@@ -0,0 +1,14 @@
+USING: help.markup help.syntax ;
+IN: math.erato
+
+HELP: <erato>
+{ $values { "n" "a positive number" } { "erato" "a prime numbers generator" } }
+{ $description "Build a prime numbers generator for primes between 2 and " { $snippet "n" } " (inclusive)." } ;
+
+HELP: next-prime
+{ $values { "erato" "a generator" } { "prime/f" "a prime number or f" } }
+{ $description "Compute the next prime number using the given generator. If there are no more prime numbers under the limit used when building the generator, f is returned instead." } ;
+
+HELP: lerato
+{ $values { "n" "a positive number" } { "lazy-list" "a lazy prime numbers generator" } }
+{ $description "Builds a lazy list containing the prime numbers between 2 and " { $snippet "n" } " (inclusive). Lazy lists are described in " { $link "lazy-lists" } "." } ;

diff --git a/extra/math/erato/erato-tests.factor b/extra/math/erato/erato-tests.factor
new file mode 100644 (file)
index 0000000..6e961b9
--- /dev/null
+++ b/extra/math/erato/erato-tests.factor
@@ -0,0 +1,6 @@
+! Copyright (c) 2007 Samuel Tardieu.
+! See http://factorcode.org/license.txt for BSD license.
+USING: lazy-lists math.erato tools.test ;
+IN: temporary
+
+[ { 2 3 5 7 11 13 17 19 } ] [ 20 lerato list>array ] unit-test

diff --git a/extra/math/erato/erato.factor b/extra/math/erato/erato.factor
new file mode 100644 (file)
index 0000000..eb081f1
--- /dev/null
+++ b/extra/math/erato/erato.factor
@@ -0,0 +1,34 @@
+! Copyright (c) 2007 Samuel Tardieu.
+! See http://factorcode.org/license.txt for BSD license.
+USING: bit-arrays kernel lazy-lists math math.functions math.ranges sequences ;
+IN: math.erato
+
+TUPLE: erato limit bits latest ;
+
+<PRIVATE
+
+: mark-multiples ( n erato -- )
+  over sqrt over erato-limit <=
+  [
+    [ erato-limit over <range> ] keep
+    erato-bits [ set-nth ] curry f -rot curry* each
+  ] [
+    2drop
+  ] if ;
+
+PRIVATE>
+
+: <erato> ( n -- erato )
+  dup 1 + <bit-array> 1 over set-bits erato construct-boa ;
+
+: next-prime ( erato -- prime/f )
+  [ erato-latest 1+ ] keep [ set-erato-latest ] 2keep
+  2dup erato-limit <=
+  [
+    2dup erato-bits nth [ dupd mark-multiples ] [ nip next-prime ] if
+  ] [
+    2drop f
+  ] if ;
+
+: lerato ( n -- lazy-list )
+  <erato> [ next-prime ] keep [ nip next-prime ] curry lfrom-by [ ] lwhile ;

diff --git a/extra/math/erato/summary.txt b/extra/math/erato/summary.txt
new file mode 100644 (file)
index 0000000..e8982fa
--- /dev/null
+++ b/extra/math/erato/summary.txt
@@ -0,0 +1 @@
+Sieve of Eratosthene