[Tutor] MemoryError

[Satya Luzy]

Thanks for testing out more of the program.
Yes, as you can see, I'm using the continued fraction method on n, which in
your case is 459.
During the continued fraction process (referring to function
cfract(n,boundary)), I set the boundary to store only 50 value of the first
iteration. The result of that function can be in a short pattern, just like
what you have seen:
[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]
In this case, the algorithm may get nothing or fail in this step because of
q (not Q) value. Thus, variable j is introduced.
When it comes to this, my code will move to faktorisasi function.
Fulfilling a mathematical rule where 459 = k.459 (mod n). The k is
multiplication, which is represented by j. Thus my program when it failed
on the first try, it will increase both the boundary and k or j until it
found the match. In faktorisasi_default function, it is creating one table
that consists of q,P,Q,A. The j variable is for the next table generation.

I will try more cases on my unfinished program.
Meanwhile, please bear with my amateurishness.
Thanks

On Wed, Dec 30, 2015 at 1:36 PM, Steven D'Aprano <steve at pearwood.info>
wrote:

> 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
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>