Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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)

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)

print pollard_Rho(7331118)

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)

print pollard_Rho(7331118)

Fixed indentation.