On 29/12/15 17:00, Satya Luzy wrote: > Hello, > 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
To be honest this is probably a bit beyond the scope of the tutor list which is aimed at questions about the Python language and standard library. However I'll make a few observations (and assume your logic is OK since you did test it on some smaller data first) > --------------------------------------------------------------------------------------------------------------------- > *Traceback (most recent call last):* > * File "C:/Users/Satya/PycharmProjects/untitled2/fact.py", line 94, in > <module>* > * faktorisasi(n)* > * File "C:/Users/Satya/PycharmProjects/untitled2/fact.py", line 92, in > faktorisasi* > * faktorisasi_default(n,j,boundary)* > * File "C:/Users/Satya/PycharmProjects/untitled2/fact.py", line 55, in > faktorisasi_default* > * Q.append(((n*kelipatan)-(p[i]**2))/Q[i-1])* > *MemoryError* There's not much of a clue in the error message but there are several things we can note about your code, which if cleaned up would make it easier to test/debug and also might reduce the memory consumption. I don't know if any of these suggestions will help with the memory error but clarity of code can only help think about the problem. First you communicate between functions with globals, it would be better to return values. (For example the flag that only exists to be set in the faktorisasi_default code so that it influences the faktorisasi while loop.) Second you have a lot of loops that all appear to be looping over the same basic data set. Is it possible to combine the processing of those loops in some way? Alternatively could you refactor the code to break the loops into separate functions so that the higher level algorithm is clearer? Third you have a lot of intermediate variables that seem to add little value but clutter the code. (see below) > import fractions > import math > > n = 94152743499601547 #untuk difaktorkan > flag = True > faktor_1 = 1 #deklarasi asal > faktor_2 = 1 > > # 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): > global faktor_1,faktor_2,flag > > q = cfract(n*kelipatan,boundary) > p = [] > Q = [] > A = [] > p.append(0) > p.append(q[0]) > Q.append(1) > A.append(0) > A.append(1) > A.append(q[0]) > Q.append(((n*kelipatan)-(p[1]**2))/Q[0]) You could combine these lines to include the initial values directly as: p = [0, q[0]] Q = [1, ((n*kelipatan)-(p[1]**2))/Q[0]] A = [0,1] Also since it appears more than once you could assign def f(n,k): return ((n*k)-(p[1]**2))/Q[0] Where you can hopefully think of a better name than 'f'... > > # 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 > > temp = 0 # nilai Q yg ganda > temp2 = 0 > tempA1 = 0 # nilai A dari Q1 > tempA2 = 0 # nilai A dari Q2 Since you don;t use these before assigning them below you don't really need to initialise them here in the middle of your algorithm. Just create them by assigning to them later. > for i in range(0,len(Q)): > for j in range(i+1,len(Q)): These loops look suspicious to me. They both loop over the same data range and look like they do an awful lot of work on the same basic data. Could they be rationalised? I may be wrong, I haven't a clue about what the algorithm is supposed to do. It just feels odd somehow. > 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 Do you really gain anything with the tempA variables? Why not just use temp2 = A[i+1] * A[j+1] % n > 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 > This is where I mentioned the flag being used to communicate between functions. Could you not return False here since the loop will do no more work after the flag is set (but may continue to iterate for quite some time) If the outer loop completes without returning False then you can return true.... I think... > def faktorisasi(n): > global flag > j=1 #kelipatan > boundary=50 #iterasi CFRAC > faktorisasi_default(n,j,boundary) > while (flag): This would then become while faktorisasi_default(n,j,boundary): j+=1 boundary*=2 print "Nilai boundary : %d" %boundary print "Nilai j : %d" %j As I say I don't know if any of that will help with the memory error but it should improve clarity at least a little. -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ http://www.amazon.com/author/alan_gauld Follow my photo-blog on Flickr at: http://www.flickr.com/photos/alangauldphotos _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor