Sure, here are the patches (Rupert's included)
Jon
From d5b628d64f352875755b3070300a5037712f6796 Mon Sep 17 00:00:00 2001
From: Rupert Swarbrick <rswarbr...@gmail.com>
Date: Thu, 21 Oct 2010 11:49:13 +0100
Subject: [PATCH 1/2] math.primes.erato: Fix off-by-one error
The sieve bit vector deals with numbers in chunks of 30. Therefore,
the number 90 (say) is the 91st 'element' of the vector. Each byte
deals with some range {0,1,...,29}+30n so to have the number 90, you
need four bytes.
Rather pleasingly, I bumped into this bug and it reduced to the
incantation:
2010 2010 sieve marked-prime?
---
basis/math/primes/erato/erato-tests.factor | 8 +++++++-
basis/math/primes/erato/erato.factor | 2 +-
2 files changed, 8 insertions(+), 2 deletions(-)
diff --git a/basis/math/primes/erato/erato-tests.factor b/basis/math/primes/erato/erato-tests.factor
index e6f7765..ff44ec2 100644
--- a/basis/math/primes/erato/erato-tests.factor
+++ b/basis/math/primes/erato/erato-tests.factor
@@ -1,4 +1,5 @@
-USING: byte-arrays math math.bitwise math.primes.erato sequences tools.test ;
+USING: kernel byte-arrays sequences tools.test ;
+USING: math math.bitwise math.ranges math.primes.erato ;
[ B{ 255 251 247 126 } ] [ 100 sieve ] unit-test
[ 1 100 sieve marked-prime? ] [ bounds-error? ] must-fail-with
@@ -8,3 +9,8 @@ USING: byte-arrays math math.bitwise math.primes.erato sequences tools.test ;
! There are 25997 primes below 300000. 1 must be removed and 3 5 7 added.
[ 25997 ] [ 299999 sieve [ bit-count ] map-sum 2 + ] unit-test
+
+! Check sieve array length logic by making sure we get the right
+! end-point for numbers with all possibilities mod 30. If something
+! were to go wrong, we'd get a bounds-error.
+[ ] [ 2 100 [a,b] [ dup sieve marked-prime? drop ] each ] unit-test
diff --git a/basis/math/primes/erato/erato.factor b/basis/math/primes/erato/erato.factor
index fdc2f9f..4df724c 100644
--- a/basis/math/primes/erato/erato.factor
+++ b/basis/math/primes/erato/erato.factor
@@ -28,7 +28,7 @@ CONSTANT: masks B{ 0 128 0 0 0 0 0 64 0 0 0 32 0 16 0 0 0 8 0 4 0 0 0 2 0 0 0 0
2drop
] if ;
-: init-sieve ( n -- arr ) 29 + 30 /i 255 <array> >byte-array ;
+: init-sieve ( n -- arr ) 30 /i 1 + 255 <array> >byte-array ;
PRIVATE>
--
1.7.0.4
From 682d0bf3d51d726e3ba7ed5e4f843225e6c7f442 Mon Sep 17 00:00:00 2001
From: Jon Harper <jon.harpe...@gmail.com>
Date: Tue, 2 Nov 2010 17:23:54 +0100
Subject: [PATCH 2/2] math.primes.erato doc fixes.
---
basis/math/primes/erato/erato-docs.factor | 14 +++++++++-----
1 files changed, 9 insertions(+), 5 deletions(-)
diff --git a/basis/math/primes/erato/erato-docs.factor b/basis/math/primes/erato/erato-docs.factor
index 75e3846..b9d9ea3 100644
--- a/basis/math/primes/erato/erato-docs.factor
+++ b/basis/math/primes/erato/erato-docs.factor
@@ -1,10 +1,14 @@
-USING: help.markup help.syntax ;
+USING: byte-arrays help.markup help.syntax kernel math ;
IN: math.primes.erato
HELP: sieve
-{ $values { "n" "the greatest odd number to consider" } { "arr" "a bit array" } }
-{ $description "Apply Eratostene sieve up to " { $snippet "n" } ". Primality can then be tested using " { $link marked-prime? } "." } ;
+{ $values { "n" integer } { "arr" byte-array } }
+{ $description "Apply Eratostene sieve up to " { $snippet "n" }
+". " { $snippet "n" } " must be greater than 1"
+". Primality can then be tested using " { $link marked-prime? } "." } ;
HELP: marked-prime?
-{ $values { "n" "an integer" } { "arr" "a byte array returned by " { $link sieve } } { "?" "a boolean" } }
-{ $description "Check whether an odd integer between 3 and the limit given to " { $link sieve } " has been marked as a prime number."} ;
+{ $values { "n" integer } { "arr" byte-array } { "?" boolean } }
+{ $description "Checks whether " { $snippet "n" } " has been marked as a prime number. "
+{ $snippet "arr" } " must be " { $instance byte-array } " returned by " { $link sieve } ". "
+{ $snippet "n" } " must be between 2 and the limit given to " { $link sieve } "." } ;
--
1.7.0.4
------------------------------------------------------------------------------
Nokia and AT&T present the 2010 Calling All Innovators-North America contest
Create new apps & games for the Nokia N8 for consumers in U.S. and Canada
$10 million total in prizes - $4M cash, 500 devices, nearly $6M in marketing
Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to Ovi Store
http://p.sf.net/sfu/nokia-dev2dev
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
