Primality tests, division, etc. (was :Re: [squeak-dev] The Trunk: Kernel-dtl.381.mcz)

> 2010/1/23 Levente Uzonyi <[hidden email]>:
>> On Sat, 23 Jan 2010, [hidden email] 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!
>>>
>>>
>>>
>>
>>
>
>