Issue 5249 in pharo: isPrime tests failing

Status: FailingTest
Owner: [hidden email]
Labels: Type-Bug

New issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Faling tests:

  IntegerTest>>testIsPrime
  IntegerTest>>testIsPrime2
  IntegerTest>>testIsProbablyPrime


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #1 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

I think we  need to port Integer >> #raisedTo:modulo: from squeak as well.

The current method does not properly normalize Integers, so it fails when a  
LargeInt representation of 1 is compared to a SmallInt one... (\\\ as used  
by the current version states it's intended for DSA, in which I guess you  
never treat the result from an equality perspective, and thus can live with  
non-normalized integers... )


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #2 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Ok thanks for the information.


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Labels: Milestone-1.4

Comment #3 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

(No comment was entered for this change.)


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #4 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Squeak use a Montgomery exponentiation
http://en.wikipedia.org/wiki/Montgomery_reduction

And a sliding window exponentiation algorithm.
This means the powers corresponding to some bit patterns are pre-computed.
Exponentiation is then performed by bit packets, rather than bit by bit.
Statistically, this reduce the number of operations.
http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Sliding_window_method


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #5 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Thanks for the explanation but what is the missing method I forgot to  
integrate?

Stef


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #6 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Integer>>raisedTo: n modulo: m
        "Answer the modular exponential.
        Note: this implementation is optimized for case of large integers raised  
to large powers."
        | a s mInv |
        n = 0 ifTrue: [^1].
        (self >= m or: [self < 0]) ifTrue: [^self \\ m raisedTo: n modulo: m].
        n < 0 ifTrue: [^(self reciprocalModulo: m) raisedTo: n negated modulo: m].
        (n < 4096 or: [m even])
                ifTrue:
                        ["Overhead of Montgomery method might cost more than naive divisions,  
use naive"
                        ^self slidingLeftRightRaisedTo: n modulo: m].
       
        mInv := 256 - ((m bitAnd: 255) reciprocalModulo: 256).

        "Initialize the result to R=256 raisedTo: m digitLength"
        a := (1 bitShift: m digitLength*8) \\ m.
       
        "Montgomerize self (multiply by R)"
        (s := self montgomeryTimes: (a*a \\ m) modulo: m mInvModB: mInv)
                ifNil:
                        ["No Montgomery primitive available ? fallback to naive divisions"
                        ^self slidingLeftRightRaisedTo: n modulo: m].

        "Exponentiate self*R"
        a := s montgomeryRaisedTo: n times: a modulo: m mInvModB: mInv.

        "Demontgomerize the result (divide by R)"
        ^a montgomeryTimes: 1 modulo: m mInvModB: mInv


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Status: FixToInclude

Comment #7 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

(No comment was entered for this change.)


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #8 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Nicolas I saw that

montgomeryTimes: a modulo: m mInvModB: mInv
        "Answer the result of a Montgomery multiplication
        self * a * (256 raisedTo: m digitLength) inv \\ m
        NOTE: it is assumed that:
        self digitLength <= m digitLength
        a digitLength <= m digitLength
        mInv * m \\ 256 = (-1 \\ 256) = 255 (this implies m odd)
       
        Answer nil in case of absent plugin or other failure."
       
        <primitive: 'primMontgomeryTimesModulo' module:'LargeIntegers'>
        ^nil

is this primitive in all the plugin.

Then I do not understand why changing the implementation of raisedTo:  
modulo: changes the prime computation. I'm probably too stupid to  
understand that but to me raisedTo: modulo: should return a correct result  
and based on it the prime computation too. What did I miss?






_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Status: Closed

Comment #9 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

in 14329


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #10 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Yes, the primitive has been integrated both in traditional Interpreter and  
in COG branch. The code still works if the primitive is absent (case of old  
VM), but of course slower.

For the reason to use modular arithmetic, I gave some references in Issue  
4997 See
http://en.wikipedia.org/wiki/Primality_test

As for what you did wrong, nothing, it's just that some pre-existing  
methods violate this invariant:
LargePositiveInteger allSubInstances allSatisfy: [:e | e normalize == e]

One such method which produces un-normalized integers is \\\



_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #11 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Ah, but due to SmalltalkImage>>recreateSpecialObjectsArray the invariant is

LargePositiveInteger allSubInstances allSatisfy: [:e | e normalize == e or:  
[e == (Smalltalk specialObjectsArray at: 33)]].


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #12 on issue 5249 by [hidden email]: isPrime tests failing
http://code.google.com/p/pharo/issues/detail?id=5249

Thanks


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker