--- a/Integer.st Fri Feb 06 15:07:32 2009 +0100
+++ b/Integer.st Sat Feb 07 14:22:25 2009 +0100
@@ -13,7 +13,7 @@
Number subclass:#Integer
instanceVariableNames:''
- classVariableNames:'DefaultDisplayRadix BCDConversionErrorSignal'
+ classVariableNames:'DefaultDisplayRadix BCDConversionErrorSignal PrimeCache'
poolDictionaries:''
category:'Magnitude-Numbers'
!
@@ -798,6 +798,34 @@
!Integer class methodsFor:'prime numbers'!
+flushPrimeCache
+ "cleanup after using a primeCache"
+
+ PrimeCache := nil.
+
+ "
+ Integer initializePrimeCacheUpTo:1000000
+ Integer flushPrimeCache.
+ "
+!
+
+initializePrimeCacheUpTo:limit
+ "if many operations are to be done using primes, we can keep them around..."
+
+ |bits|
+
+ bits := BooleanArray new:limit.
+ self primesUpTo:limit do:[:p |
+ bits at:p put:true
+ ].
+ PrimeCache := bits.
+
+ "
+ Integer initializePrimeCacheUpTo:1000000
+ Integer flushPrimeCache.
+ "
+!
+
largePrimesUpTo: max do: aBlock
"Evaluate aBlock with all primes up and including maxValue.
The Algorithm is adapted from http://www.rsok.com/~jrm/printprimes.html
@@ -876,10 +904,25 @@
"
!
+primesUpTo1000
+ "/ primes up to 1000
+
+ ^ #(
+ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
+ 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191
+ 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283
+ 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401
+ 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509
+ 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631
+ 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751
+ 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877
+ 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997).
+!
+
primesUpTo: max
"Return a list of prime integers up to abd including the given integer."
- ^Array streamContents:[:s| self primesUpTo: max do:[:prime| s nextPut: prime]]
+ ^ Array streamContents:[:s| self primesUpTo: max do:[:prime| s nextPut: prime]]
"
Integer primesUpTo: 100
@@ -960,6 +1003,26 @@
| limit flags prime k |
+ PrimeCache notNil ifTrue:[
+ max <= PrimeCache size ifTrue:[
+ 2 to:max do:[:p |
+ (PrimeCache at:p) ifTrue:[
+ aBlock value:p
+ ].
+ ].
+ ^ self.
+ ].
+ ].
+
+ max <= 1000 ifTrue:[
+ "/ primes up to 2500
+ self primesUpTo1000 do:[:p |
+ p > max ifTrue:[^ self].
+ aBlock value:p.
+ ].
+ ^ self.
+ ].
+
limit := max asInteger - 1.
"Fall back into #largePrimesUpTo:do: if we'd require more than 100k of memory;
the alternative will only requre 1/154th of the amount we need here and is almost as fast."
@@ -3635,23 +3698,17 @@
|limit firstFewPrimes|
+ self <= PrimeCache size ifTrue:[
+ ^ PrimeCache at:self.
+ ].
+
self even ifTrue:[^ self == 2 ].
self == 1 ifTrue:[^ false ].
limit := self sqrt.
"/ primes up to 1000
- firstFewPrimes := #(
- 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
- 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191
- 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283
- 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401
- 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509
- 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631
- 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751
- 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877
- 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997).
-
+ firstFewPrimes := self class primesUpTo1000.
firstFewPrimes do:[:p |
p > limit ifTrue:[^ true].
(self \\ p) == 0 ifTrue:[ ^ false ].
@@ -3667,6 +3724,7 @@
(1 to:1000000) count:[:n | n isPrime] 78498
Time millisecondsToRun:[ (1 to:1000000) count:[:n | n isPrime]] 1295 w.o firstFewPrimes
Time millisecondsToRun:[ (1 to:1000000) count:[:n | n isPrime]] 936 with firstFewPrimes (less tests)
+ Time millisecondsToRun:[ (1 to:1000000) count:[:n | n isPrime]] 343 with primeCache
"
!
@@ -3968,7 +4026,7 @@
!Integer class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.216 2009-02-05 13:59:29 sr Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.217 2009-02-07 13:22:25 cg Exp $'
! !
Integer initialize!