Ask Your Question
0

Applying Memoized to Recursive Function

asked 2015-10-31 22:19:28 -0500

KristofferH gravatar image

updated 2015-10-31 22:30:26 -0500

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.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2015-11-02 08:55:04 -0500

tmonteil gravatar image

Your 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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-10-31 22:19:28 -0500

Seen: 214 times

Last updated: Nov 02 '15