Sieve of eratosthene optimizations

diff --git a/extra/math/erato/erato-docs.factor b/extra/math/erato/erato-docs.factor
index e5dc82daf732ce3cf927b14468d7e8b14463df10..6e84c84057be0b2a766e00b653b344622917fcc5 100644 (file)
--- a/extra/math/erato/erato-docs.factor
+++ b/extra/math/erato/erato-docs.factor
@@ -1,14 +1,6 @@
 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.factor b/extra/math/erato/erato.factor
index eb081f19389325bf5c0d59ebf189ff49a82cc270..4993f39e44ff95bee05f4dd325841dd795f7669b 100644 (file)
--- a/extra/math/erato/erato.factor
+++ b/extra/math/erato/erato.factor
@@ -3,32 +3,36 @@
 USING: bit-arrays kernel lazy-lists math math.functions math.ranges sequences ;
 IN: math.erato
 
+<PRIVATE
+
 TUPLE: erato limit bits latest ;
 
-<PRIVATE
+: ind ( n -- i )
+  2/ 1- ; inline
 
-: 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 ;
+: is-prime ( n erato -- bool )
+  >r ind r> erato-bits nth ; inline
 
-PRIVATE>
+: indices ( n erato -- range )
+  erato-limit ind over 3 * ind swap rot <range> ;
+
+: mark-multiples ( n erato -- )
+  over sq over erato-limit <=
+  [ [ indices ] keep erato-bits [ f -rot set-nth ] curry each ] [ 2drop ] if ;
 
 : <erato> ( n -- erato )
-  dup 1 + <bit-array> 1 over set-bits erato construct-boa ;
+  dup ind 1+ <bit-array> 1 over set-bits erato construct-boa ;
 
 : next-prime ( erato -- prime/f )
-  [ erato-latest 1+ ] keep [ set-erato-latest ] 2keep
+  [ erato-latest 2 + ] keep [ set-erato-latest ] 2keep
   2dup erato-limit <=
   [
-    2dup erato-bits nth [ dupd mark-multiples ] [ nip next-prime ] if
+    2dup is-prime [ dupd mark-multiples ] [ nip next-prime ] if
   ] [
     2drop f
   ] if ;
 
+PRIVATE>
+
 : lerato ( n -- lazy-list )
-  <erato> [ next-prime ] keep [ nip next-prime ] curry lfrom-by [ ] lwhile ;
+  <erato> 2 [ drop next-prime ] curry* lfrom-by [ ] lwhile ;