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

**URL:** https://discourse.julialang.org/t/how-to-combine-binary-gcd-and-div-in-a-mutable-function/95027
**Category:** New to Julia
**Created:** [February 22, 2023, 3:32pm UTC](https://discourse.julialang.org/t/how-to-combine-binary-gcd-and-div-in-a-mutable-function/95027 "2023-02-22T15:32:50Z")
**Posts on this page:** 2
**Page:** 1

<div class="post-metadata">

### Author: ![x13420x](https://avatars.discourse-cdn.com/v4/letter/x/ecc23a/32.png) [@x13420x](https://discourse.julialang.org/u/x13420x)
#### Post date: [February 22, 2023, 3:32pm UTC](https://discourse.julialang.org/t/how-to-combine-binary-gcd-and-div-in-a-mutable-function/95027/1 "2023-02-22T15:32:50Z")

</div>

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?

```julia
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](https://github.com/JuliaLang/julia/blob/master/base/intfuncs.jl)

---

<div class="post-metadata">

### Author: ![x13420x](https://avatars.discourse-cdn.com/v4/letter/x/ecc23a/32.png) [@x13420x](https://discourse.julialang.org/u/x13420x)
#### Post date: [February 23, 2023, 5:55pm UTC](https://discourse.julialang.org/t/how-to-combine-binary-gcd-and-div-in-a-mutable-function/95027/2 "2023-02-23T17:55:38Z")

</div>

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.