[Tutor] Actual code that illustrates problem

[Kermit Rose]

Alan Gauld wrote:
>
> While others have made good suggestions to clarify the code I thought
> I'd try to tackle the question of whether we had a bug in Python.
>
> Unfortunately the debug output does not come from the code that's
> posted so its difficult to figure out what's been happening.
>
> For example, one apparently good and one "faulty" test:
>
>>  In strongfac
>>  Found1: x =  53799857
>>  Found1: y =  1858741
>>  face =  [53799857L, 1858741L, 0]
>>  Found1: factor by strong probable prime test, using witnes 
>> 15306543515214
>
> Note the mis-spelling of witnes(sic) - it does not appear in the code!
>
Hmm....    Perhaps I caught that spelling error between the time I sent 
the attached program file and the time I reran the program to demostrate 
the error.


>>  Found1: factors are  53799857 1858741
>>  Found1: returning  [53799857L, 1858741L, 0]  to fermat routine.
>>  Retrieved from strongfac, face =  [0, 0, 0]
>>  In fermat: k =  13  x =  0  y =  0  face =  [0, 0, 0]
>
> Similarly the first line has the text "factors are 53..."
>
> But in the code all instances of "factors are" are followed by the 
> word "by"
>
> So I conclude the tests are not from this code. The fault may be in 
> this code
> but I can't be sure...
>
After I've followed the many good suggestions for making my program more 
concise and readable,
I'll re-run it and see if I get the same difficulty at the same z's to 
factor.

I will upload the source to my web page and create a path to it in my 
index.html file.


> However a couple of observations might help:
>
>> #    def strongfac(z,w):
>> #        x = gcd(z,w-1)
>> #        if x > 1:
>> #            if x < z:
>
> You can simpliffy this 2 stage test using either boolean operartors:
>
> if x > 1 and x < z:
>
> OR, almost uniquie to pyhon:
>
> if 1 < x < z:
>

Hmmmmmm.

A good syntax to remember.


> That removes one whole layer of indentation.
> This trick can be applied in many places in the algorithm.
>
>
> Also
>
>
>> #                y = z/x
>> #                print "Found factors by P-1 Method as part of Strong
>> probable prime test, using witness",w,"."
>> #                print " x = ",x," y = ",y
>> #                return [x,y,0]
>> #        w2 = (w * w)%z
>> #        s = ksqrt(w2)
>> #        if w2 == s * s:
>> #            if s != w:
>> #                x = gcd(z,kabs(w2 - s))
>> #                if x > 1:
>> #                    if x < z:
>> #                        print "Found factors by square = square as 
>> part of
>> Strong probable prime test, using witness",w,"."
>> #                        return [x,y,0]
>
> If x was not between 1 and z in the first test y is not defined at 
> this point.
>
Yep.  I should have calculated y = z/x before printing.

The syntax checker would have found this as soon as I encountered a z 
that took me to that point.

I'll fix it before re-submitting.


>> #        trace = 0
>> #        t = z - 1
>> #        a = 0
>> #        while t%2 == 0:
>> #            t = t/2
>> #            a = a + 1
>> #        test = pow(w,t,z)
>> #        if test ==1:
>> #            x = gcd(z,w-1)
>> #            if x > 1:
>> #                if x < z:
>> #                    y = z/x
>> #                    print " Found factor by Strong probable prime test,
>> using withness ",w,"."
>> #                    return [x,y,0]
>> #        else:
>> #            x = gcd(test-1,z)
>> #            if x > 1:
>> #                print " "
>> #                print " In strongfac "
>> #                print " Found1: x = ",x
>
> You could do all of this with a single print:
>
> print "\n In strongfac \nFound1: x = ", x
>
uuuuuuuuuh..     Too compact for me.

I need to see the logic more spread out.



> I won't go any further because its pointless given the discrepency 
> between
> the data and the code, but hopefully those pointers will be helpful in 
> your
> efforts to tidy the code into separate functions.
>
> Alan G.

Also a warning to me to not edit the final output to compensate for 
faulty programming.

Thank you.

Kermit  <   kermit at polaris.net   >