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 < [EMAIL PROTECTED] > _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor