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:
>> http://source.squeak.org/trunk/Kernel-dtl.381.mcz
>>
>> ==================== 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...

Nicolas

> 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?
>
>
> Levente
>
>>
>> Rationale for use of probabilistic algorithm provided by Enrico Spinielli:
>>
>>  http://lists.squeakfoundation.org/pipermail/squeak-dev/2009-December/142372.html
>>
>> =============== Diff against Kernel-nice.380 ===============
>>
>> Item was changed:
>>  ----- Method: Integer>>isPrime (in category 'testing') -----
>>  isPrime
>> +       "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 ] ].
>>        ^true!
>>
>> 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!
>>
>>
>>
>
>