[squeakdev] The Trunk: Kernelnice.653.mcz
commits at source.squeak.org
commits at source.squeak.org
Tue Nov 15 22:24:26 UTC 2011
Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernelnice.653.mcz
==================== Summary ====================
Name: Kernelnice.653
Author: nice
Time: 15 November 2011, 11:23:38.908 pm
UUID: d149a4f7f5374f769b79367acd0aa832
Ancestors: Kernellaza.649
Minor refactoring of isProbablyPrime
 Add more comments (tell it's a Miller Rabin test, tells about probabilities)
 avoid repeated shift when #lowBit can help doing it once
 refactor Knuth "P3" test to a simpler expression
 and restore the fact that there is a step "P4" before "P5"
=============== Diff against Kernellaza.649 ===============
Item was changed:
 Method: Integer>>isProbablyPrime (in category 'testing') 
isProbablyPrime
"See isProbablyPrimeWithK:andQ: for the algoritm description."
 k q 
self <= 1 ifTrue: [ ^false ].
self even ifTrue: [ ^self = 2 ].
+ "Factor self into (2 raisedTo: k) * q + 1, where q odd"
+ q := self bitShift: 1.
+ k := q lowBit.
+ q := q bitShift: 1  k.
+ "Repeat the probabilistic until false (the probability of false negative is null) or until probability is very low."
 k := 1.
 q := self  1 bitShift: 1.
 [ q odd ] whileFalse: [
 q := q bitShift: 1.
 k := k + 1 ].
25 timesRepeat: [ (self isProbablyPrimeWithK: k andQ: q) ifFalse: [ ^false ] ].
+ "The probability of false positive after 25 iterations is less than (1/4 raisedTo: 25) < 1.0e15"
^true!
Item was changed:
 Method: Integer>>isProbablyPrimeWithK:andQ: (in category 'private') 
isProbablyPrimeWithK: k andQ: q
"Algorithm P, probabilistic primality test, from
Knuth, Donald E. 'The Art of Computer Programming', Vol 2,
+ Third Edition, section 4.5.4, page 395, P1P5 refer to Knuth description..
+ Note that this is a Miller Rabin test which may answer false positives (known as pseudoprimes) for at most 1/4 of the possible bases x."
 Third Edition, section 4.5.4, page 395, P1P5 refer to Knuth description."
+  x j y minusOne 
"P1"

  x j y 
x := (self  2) atRandom + 1.
"P2"
j := 0.
y := x raisedTo: q modulo: self.
+ minusOne := self  1.
 "P3"
+ ["P3"
+ y = 1 ifTrue: [^j = 0].
+ y = minusOne ifTrue: [^true].
+ "P4"
+ (j := j + 1) < k]
+ whileTrue:
+ [y := y squared \\ self].
 [((j = 0 and: [y = 1]) or: [y = (self  1)]) ifTrue: [^true].
 (j > 0 and: [y = 1]) ifTrue: [^false].
"P5"
+ ^false!
 j := j + 1.
 j < k
 ifTrue: [y := y squared \\ self]
 ifFalse:[^ false]] repeat!
More information about the Squeakdev
mailing list
