[Tutor] MemoryError

[Alan Gauld]

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