# 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[1],y[y],true) should change the values of x[1] and y[1]. 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[1]=za>zb
if bo[1]
k[1]=za-zb
else
k[1]=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[1]
am = am<<k[1]
else
bm = bm<<k[1]
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.