Let us say I have a function called
my_func(a,b,s,t). Suppose, I want
b to be passed by value, but I want
t to be passed by reference. As in, I want to some how pass in let us say
(4,5,s',t'). The function performs computations by calling
my_func(a/2,b/2,s/2,t/2). The thing is, there is a base case at the “bottom” of the recursion that gives concrete values to
Let me give a mini example:
def e_euclid(a,b,s,t): if (a == b): s = 4 t = -3 return a if (a%2 == 0 and b%2 == 0): if (s%2 == 0 and t%2 == 0): return 2*e_euclid(a/2,b/2,s/2,t/2) else: return 2*e_euclid(a/2,b/2,(s+b)/2,(t-a)/2) ...
So, I would call this function as
e_euclid(a,b, something, something) but then I would have to supply concrete values for
t. Can you guys kind of see what I’m trying to do here?
Doing recursion where I return (s,t) would lead to a tough computation that I don’t wish to perform, so I would like to do it this way.
Your code seems broken, already that base case (?) with
a == b and
s = 4 and
t = -3 doesn’t make sense. But see this C++ implementation and my Python translation using single-element lists instead of C++’s references:
def gcd(a, b, x=[None], y=[None]): if b == 0: x = 1 y = 0 return a x1, y1 = [None], [None] d = gcd(b, a % b, x1, y1) x = y1 y = x1 - y1 * (a // b) return d a, b = 123, 321 x, y = [None], [None] print(gcd(a, b, x, y), x, y, a*x + b*y)
Output (Try it online!):
3  [-18] 3
I think you’re trying to use the binary version of the algorithm, that should be doable the same way.