Primality tests, division, etc. (was :Re: [squeak-dev] The Trunk:
nicolas.cellier.aka.nice at gmail.com
Sat Jan 23 20:45:10 UTC 2010
2010/1/23 Levente Uzonyi <leves at elte.hu>:
> On Sat, 23 Jan 2010, commits at source.squeak.org wrote:
>> David T. Lewis uploaded a new version of Kernel to project The Trunk:
>> ==================== Summary ====================
>> Name: Kernel-dtl.381
>> Author: dtl
>> Time: 23 January 2010, 2:56:10.622 pm
>> UUID: 70c5d3fd-a468-4289-b9b5-101cdaea72b8
>> Ancestors: Kernel-nice.380
>> Use probabilistic algorithm (Knuth) for testing primality of large
>> integers, and add method comments for explanation.
> The algorithm is a Miller-Rabin primality test with 25 as the accuracy
> parameter. This means that the chance for a false positive is less than 4
> raisedTo: -25. DSA uses the same algorithm, but requires the parameter to be
> at least 50 IIRC, you can find the other implementation at:
> DigitalSignatureAlgorithm >> #isProbablyPrime:.
> I was digging into the code and tried possible improvements, but got stuck
> at a point. I found that there are two methods for the same problem:
> #raisedTo:modulo: and #raisedToInteger:modulo:. They do the same, but the
> latter is a lot slower, because the first one uses #\\\ instead of #\\ which
> uses #digitDiv:neg: (a division primitive).
> I found that #digitDiv:neg: works with any Integer, while primitive 31 (used
> by #\\) only works if the argument and the result are both less than 2
> raisedTo: 30, otherwise it will fall back to Smalltalk code which happens
> most of the time in these primality tests.
I tried an alternative here http://bugs.squeak.org/view.php?id=7120
but not really succesfull...
> For a final solution we should decide what to do.
> - what should we do with #raisedTo:modulo: and #raisedToInteger:modulo: ?
> - should (can) we replace the implementation of LargePositiveInteger >> #\\
> (and #//) with #digitDiv:neg: + #normalize or something similar?
>> Rationale for use of probabilistic algorithm provided by Enrico Spinielli:
>> =============== Diff against Kernel-nice.380 ===============
>> Item was changed:
>> ----- Method: Integer>>isPrime (in category 'testing') -----
>> + "Answer true if the receiver is a prime number. See
>> isProbablyPrime for a probabilistic
>> + implementation that is much faster for large integers, and that is
>> correct to an extremely
>> + high statistical level of confidence (effectively deterministic)."
>> self <= 1 ifTrue: [ ^false ].
>> self even ifTrue: [ ^self = 2].
>> 3 to: self sqrtFloor by: 2 do: [ :each |
>> self \\ each = 0 ifTrue: [ ^false ] ].
>> Item was added:
>> + ----- Method: LargePositiveInteger>>isPrime (in category 'testing')
>> + isPrime
>> + "Answer true if the receiver is a prime number. Use a
>> probabilistic implementation that
>> + is much faster for large integers, and that is correct to an
>> extremely high statistical
>> + level of confidence (effectively deterministic)."
>> + ^ self isProbablyPrime!
More information about the Squeak-dev