[Tutor] MemoryError

Martin A. Brown martin at linux-ip.net
Tue Dec 29 21:29:00 EST 2015


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/


More information about the Tutor mailing list