ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 02 Nov 2015 15:55:04 +0100Applying Memoized to Recursive Functionhttps://ask.sagemath.org/question/30384/applying-memoized-to-recursive-function/Does anyone know how to apply memoized function to a recursive function? specifically the def f(xn) function in the following function?
I am trying to improve the following code to be able to factor a numbers. It seems to work well for values like 7331116 and 7331118 but 7331117 results in a recursion depth error and I can't figure out how to improve the code. Someone suggested to me to memoize the def f(xn) function but all can find online is that you add @CachedFunction right before the function is declared but it doesn't seem to help.
def pollard_Rho(n):
def f(xn):
# This calculates f(x) = x^2+1 based on x0=2.
return (1 + f(xn-1)**2)%n if xn else 2
i=0 # Counting variable
x=f(i) # calculating x of the pollard rho method.
y=f(f(i)) # calculating y of the pollard rho method.
d=gcd(abs(x-y),n) # calculating gcd to construct loop.
while d==1: # A loop looking for a non 1 interesting gcd.
i = i + 1 # counting iterations
d=gcd(abs(x-y),n)
print d # Printing d=gcd for debugging purposes.
root1=d # Yes! found a factor, now we can find the other one.
root2=n/d # Hey! Here is the other factor!
print i + 1 # debugging print out.
return (root1,root2) # Kick those factors out into the world.
print pollard_Rho(7331118)
Fixed indentation.Sun, 01 Nov 2015 04:19:28 +0100https://ask.sagemath.org/question/30384/applying-memoized-to-recursive-function/Answer by tmonteil for <p>Does anyone know how to apply memoized function to a recursive function? specifically the def f(xn) function in the following function?</p>
<p>I am trying to improve the following code to be able to factor a numbers. It seems to work well for values like 7331116 and 7331118 but 7331117 results in a recursion depth error and I can't figure out how to improve the code. Someone suggested to me to memoize the def f(xn) function but all can find online is that you add @CachedFunction right before the function is declared but it doesn't seem to help. </p>
<p>def pollard_Rho(n):</p>
<pre><code>def f(xn):
# This calculates f(x) = x^2+1 based on x0=2.
return (1 + f(xn-1)**2)%n if xn else 2
i=0 # Counting variable
x=f(i) # calculating x of the pollard rho method.
y=f(f(i)) # calculating y of the pollard rho method.
d=gcd(abs(x-y),n) # calculating gcd to construct loop.
while d==1: # A loop looking for a non 1 interesting gcd.
i = i + 1 # counting iterations
d=gcd(abs(x-y),n)
print d # Printing d=gcd for debugging purposes.
root1=d # Yes! found a factor, now we can find the other one.
root2=n/d # Hey! Here is the other factor!
print i + 1 # debugging print out.
return (root1,root2) # Kick those factors out into the world.
</code></pre>
<p>print pollard_Rho(7331118)</p>
<p>Fixed indentation.</p>
https://ask.sagemath.org/question/30384/applying-memoized-to-recursive-function/?answer=30403#post-id-30403Your code is probably not well copied since the function `f` directly returns something, so what is after that will never be executed.
Anyway, here is an example on how to memoize a recursive function:
sage: @cached_function
....: def fibo(n):
....: if n == 0 or n == 1:
....: return 1
....: else:
....: return fibo(n-1) + fibo(n-2)
You can see the difference by calling `fibo(100)` with and without the `@cached_function` decorator.
Now, if you want to compute, say, `fibo(1000)`, you may encounter a `RuntimeError: maximum recursion depth exceeded`. So the trick is to fill the memory in the right order:
sage: for i in range(1000):
....: a = fibo(i)
sage: fibo(1000)
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
Mon, 02 Nov 2015 15:55:04 +0100https://ask.sagemath.org/question/30384/applying-memoized-to-recursive-function/?answer=30403#post-id-30403