[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