Hello there Satya, >I am currently working on a program to find the prime factor of n, in which >n is a big integer. Using the Continued Fraction factorization method (I >will provide the source code below, please don't mind the variables).
I do not know the Continued Fraction factorization method. (I admit to not looking it up and simply examining your code.) >It works perfectly when factorizing below 10 digits numbers. Are you certain? All 10 digit numbers? Or just the 10 digit numbers you tried? I ask because.... Well, please see my second point below. >In my code below you will see on how I tried to factorize >94152743499601547, but get this message instead : Alan, Steven and Danny have other useful comments. I will not repeat those. You may find it a bit easier to diagnose which data structure is exploding in size by logging/printing the contents of the lists p, Q and A, which you maintain in the function faktorisasi_default(). I made a few small modifications to your code (see below) so that I could run it on smaller numbers. Here are some comments: * I adjusted the variables accepted in faktorisasi_default so that there is no need for using a 'global' variable. I don't like using globals if it is possible to avoid. In pure mathematical functions, it is usually possible to avoid using a global. If you need an intermediate work product from the function (in addition to the result), then simply return the intermediate work product along with the result. * See below my (slight) modifications to your code. Now, you can see how I'm running the program to perform some more diagnosis. I think you have some sort of recursion termination problem in your functions which are implementing your factoring. In short, determining I don't think that faktorisasi_default knows when to stop. Here's how I drew this conclusion: python wuzzyluzy.py 18 # -- stops with four lines of output python wuzzyluzy.py 12275 # -- stops with four lines of output python wuzzyluzy.py 262144 # -- stops with many lines of output python wuzzyluzy.py 17 # -- never stops python wuzzyluzy.py 19 # -- never stops Good luck in your hunt for the wily factors, -Martin import fractions import math # CFRAC def cfract(n, boundary): coeff = 1 floor_part = floor_ = math.floor(math.sqrt(n)) denom = n - floor_part ** 2 result = [] result.append(int(floor_)) if float(denom)!=0: for i in range(boundary-1): try: floor_ = math.floor((math.sqrt(n) + floor_part) / float(denom)) except ZeroDivisionError: # perfect square return result if denom != 1: result.append(int(floor_)) floor_part = denom * floor_ - floor_part coeff = denom denom = n - floor_part ** 2 common_div = fractions.gcd(coeff, denom) coeff /= common_div denom /= common_div if denom == 1: result.append(int(floor_part + result[0])) return result def faktorisasi_default(n, kelipatan, boundary, faktor_1, faktor_2, flag): q = cfract(n*kelipatan, boundary) p = [0, q[0]] Q = [1] A = [0, 1, q[0]] Q.append(((n*kelipatan)-(p[1]**2))/Q[0]) # i = 2 for i in range(2,len(q)): p.append((q[i-1]*Q[i-1])-p[i-1]) Q.append(((n*kelipatan)-(p[i]**2))/Q[i-1]) A.append((q[i-1]*A[i]+A[i-1])%(n*kelipatan)) #tabel sudah selesai for i in range(0,len(Q)): for j in range(i+1,len(Q)): if flag and Q[i]==Q[j]: print Q[i] print Q[j] temp = Q[i] tempA1 = A[i+1] tempA2 = A[j+1] temp2 = tempA1*tempA2 % n # nilai base if temp2 > Q[i]: faktor_1 = int(fractions.gcd(temp2+temp, n)) faktor_2 = int(fractions.gcd(temp2-temp, n)) if faktor_1 != 1 and faktor_2 != 1: flag = False return faktor_1, faktor_2, flag def faktorisasi(n): flag = True faktor_1, faktor_2 = 1, 1 j=1 #kelipatan boundary=50 #iterasi CFRAC faktor_1, faktor_2, flag = faktorisasi_default(n, j, boundary, faktor_1, faktor_2, flag) while (flag): j+=1 boundary*=2 print "Nilai boundary : %d" %boundary print "Nilai j : %d" %j faktor_1, faktor_2, flag = faktorisasi_default(n, j, boundary, faktor_1, faktor_2, flag) return faktor_1, faktor_2 if __name__ == '__main__': import sys if len(sys.argv) > 1: n = int(sys.argv[1]) else: n = 94152743499601547 #untuk difaktorkan faktor_1, faktor_2 = faktorisasi(n) print faktor_1 print faktor_2 -- Martin A. Brown http://linux-ip.net/ _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor