[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).
[...]

I have had a bit more time available to look at this, and I don't think 
your code is correct. I changed the value of n from 94152743499601547 to 
18. Factorising 18 should give [2, 3, 3], but your code prints:

1
1
18
2


before ending. I tried it again with n = 459, which should factorise 
to [3, 3, 3, 17], but your code prints:

1
1
1
1
1
1
1
1
1
1
18
18
459
9

Then I added an extra line to the faktorisasi_default function, at the 
very end:

print 'q =', q, 'p =', p, 'Q =', Q, 'A =', A

and ran it again with n = 459 and got these results:

q = [21, 2, 2, 1, 4, 21, 4, 1, 2, 2, 42, 
         2, 2, 1, 4, 21, 4, 1, 2, 2, 42, 
         2, 2, 1, 4, 21, 4, 1, 2, 2, 42, 
         2, 2, 1, 4, 21, 4, 1, 2, 2, 42, 
         2, 2, 1, 4, 21, 4, 1, 2, 2, 42] 
p = [0, 21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21, 
        21, 15, 11, 15, 21] 
Q = [1, 18, 13, 26, 9, 2, 9, 26, 13, 18, 1, 
        18, 13, 26, 9, 2, 9, 26, 13, 18, 1, 
        18, 13, 26, 9, 2, 9, 26, 13, 18, 1, 
        18, 13, 26, 9, 2, 9, 26, 13, 18, 1, 
        18, 13, 26, 9, 2, 9, 26, 13, 18, 1] 
A = [0, 1, 21, 43, 107, 150, 248, 309, 107, 416, 21, 458, 
            438, 416, 352, 309, 211, 150, 352, 43, 438, 
        1, 21, 43, 107, 150, 248, 309, 107, 416, 21, 458, 
            438, 416, 352, 309, 211, 150, 352, 43, 438, 
        1, 21, 43, 107, 150, 248, 309, 107, 416, 21, 458]

(reformatted to make them easier to read). So you can see the problem: 
to factorise a 3 digit number, you have recorded over 200 numbers. 
And the numbers have repeating patterns, as you can see above.

I don't know if this is expected by the algorithm, or if you have made a 
programming error, but this looks very suspicious to me. At the very 
least, if you know that these repeating patterns are expected, there is 
no need to keep growing the lists and making them bigger and bigger, you 
can just build the pattern once.



-- 
Steve