# How to combine binary GCD and DIV in a mutable function

I want a mutable function that takes any two bigints and divides them by the GCD when the GCD is greater than 1. For example gcd_ab!(x,y[y],true) should change the values of x and y. Also I am interested in optimizations or complete refactoring of the code I wrote to make it faster…is it possible to write a function that is faster than the built in functions of doing gcd and then doing a division of the gcd…or 2 divisions of the gcd?

``````function gcd_ab!(a::BigInt,b::BigInt,both::Bool)::Bool
bo = trues(50)
k = zeros(Int32, 50)
za = trailing_zeros(a)
zb = trailing_zeros(b)
bo=za>zb
if bo
k=za-zb
else
k=zb-za
end
am = a>>za
bm = b>>zb
i=1
while(!(am==bm))
i+=1
bo[i]=am>bm
if bo[i]
diff=am-bm
k[i]=trailing_zeros(diff)
am = diff>>k[i]
else
diff=bm-am
k[i]=trailing_zeros(diff)
bm = diff>>k[i]
end
end
if a==1 return false
else
am=one
bm=one
end
while i>1
if bo[i]
am=bm+am<<k[i]
else
bm=am+bm<<k[i]
end
i-=1
end
if bo
am = am<<k
else
bm = bm<<k
end
a=am
if both
b=bm
end
return true
end
``````

built in gcd algorithms

My code works but I am using way too memory(100x) which could be the reason why I am getting a 100x slow down when compared to just doing 1 gcd and 2 divisions…I dont know if this code is worth trying to improve…I could put @inbounds for the arrays but I had to increase the size of the arrays to 5000…I feel my use of memory is the main inefficiency. On the positive side I am glad I learned about the trailing_zeros thing that is very helpful.