[Tutor] MemoryError

[Steven D'Aprano]

On Wed, Dec 30, 2015 at 12:00:02AM +0700, 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 (I
> will provide the source code below, please don't mind the variables). 

Are you referring to this?

http://mathworld.wolfram.com/ContinuedFractionFactorizationAlgorithm.html

> It
> works perfectly when factorizing below 10 digits numbers. In my code below
> you will see on how I tried to factorize 94152743499601547, but get this
> message instead :
> ---------------------------------------------------------------------------------------------------------------------
> *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*
> 
> *Process finished with exit code 1*
> --------------------------------------------------------------------------------------------------------------------
> It has undergone the boundary value of 51200 and j value of 12. It has been
> running for more than 5 hours before it suddenly stop.
> Please let me know how to fix the memory error,

Install lots more memory.

But really, the problem here is not the MemoryError, that is just the 
symptom. Five hours to factorise a 17 digit number is a sign that either 
your code has a bug, or that the algorithm is too inefficient. If it 
works for 10 digit numbers, I can guess that it probably doesn't have a 
bug) but the algorithm, or at least your implementation of it, is too 
inefficient. I can factorise that number in under 6 seconds:

py> print(pyprimes.factors.factorise(94152743499601547))
[6784787, 13877037481]

so it is certainly possible to do better.

Unfortunately factorisation is a hard problem, and algorithms which work 
in theory (as a mathematical process) may be too slow to be practical on 
even the fastest computer. For example, my factorise function can 
factorise 94152743499601547 in six seconds, but it might take weeks to 
factorise 8864739108501786973334779656429353 into [94152743499601627, 
94152743499601739].

So it may simply be that your code is perfectly correct, but is not 
efficient enough to deal with 17 digit numbers. For example, I see that 
your faktorisasi_default function keeps three lists, p, Q and A, which 
can grow very large. Large enough that you run out of memory.

I haven't studied either the factorization algorithm or your code enough 
to tell whether you can make it more efficient. I would need to 
understand the algorithm better to do that.



-- 
Steve