# In how many steps Euclidean Algorithm will find the GCD for two integers

I'm trying to solve this problem for big numbers (up to $10^9$). Namely, let's define $$GCD(a,b) = GCD(a-b, b)$$

We define GCD as function that returns greates common divisor of two numbers.

In case if $b > a$ we swap the values of $b$ and $a$. Now I want to count the number of steps when either $a$ or $b$ will be equal to $0$.

Example

$$a = 4, b = 17\\GCD(17, 4) = GCD(4,13)\\GCD(13,4) = GCD(4, 9)\\GCD(9,4)=GCD(5,4)\\GCD(5,4) = GCD(4, 1)\\GCD(4,1) = GCD(1,3)\\GCD(3,1) = GCD(1,2)\\GCD(2,1) = GCD(1,1)\\GCD(1,1) == GCD(0,1)$$

We have total of 8 steps, however for big values those numbers are growing super fast.

What I tried

I know that this is solvable with Euclidean algorithm for finding GCD, but the faster variant of Euclidean variant is $GCD(a,b) = GCD(b, a \text{ mod } b)$, and for this variant the number of steps is less that $\log_{10}max(a,b)$. But for this variant the number of steps is big numbers, so I think that it can be only calculated with math steps.

• This is covered in great detail on WIkipedia. Could you be more specific about what you're looking for that's not there? Sep 7 '17 at 20:02

It can be observed that the product $ab$ drops by a factor of at least two for each iteration.

Prior to each iteration, we have the pair $(a, b)$ such that $a < b$, which is replaced by the pair $(r, a)$ at the end of each iteration in preperation for the next, where $r = b \bmod a$. We then have $r < a$ and $a + r ≤ b$. Hence, $b ≥ a + r > 2r$. So, $ar < \frac{1}{2}ab$.

Supposing it takes N steps to compute $gcd(a, b)$ using the Euclidean algorithm, we then have $ar ≤ \frac{ab}{2^N}$ after N steps. It follows that $ab ≥ 2^N$.

Hence, $N ≤ \log_2 ab = \log_2 a + \log_2 b$.

Therefore, the number of steps it takes to compute $gcd(a, b)$ using the Euclidean algorithm is at most $\log_2 a + \log_2 b$.

Furthermore, on Wikipedia, you can observe that the worst case is $N ≤ 5 \log_{10} a$, i.e. five times the number of (base-10) digits of $min(a, b) = a$, where $(a, b)$ is a pair of consecutive Fibonacci numbers. This relationship is useful because $gcd(F_{n+1}, F_{n+2}) = 1$ (i.e. all consecutive Fibonacci numbers are coprime).

Given these upper-bounds, the asymptotic computational complexity of the Euclidean algorithm can be expressed using Big-O notation as $\mathcal{O}(\log b)$.

Since,

$$\mathcal{O}(\log b) = \mathcal{O}(\log_2 a + \log_2 b) = \mathcal{O}(5\log_{10} a)$$

where $b ≥ a$.

• Looking again, I guess you want it for your naive definition: $gcd(a, b) = gcd(a - b, b)$. The OP is very misleading. Sep 8 '17 at 0:50
• I will update my answer to include the naive implementation in a moment. Sep 8 '17 at 16:51

Your question is a bit vague, but here are two interpretations.

How many steps does the algorithm take in the worst case?

A pretty bad case is when $b=1$. The algorithm then takes roughly $a$ steps. This shows that for some inputs $a,b$, the algorithm takes roughly $a+b$ steps. On the other hand, $a+b$ is clearly an upper bound on the number of steps, since $a+b$ decreases in each iteration.

How to efficiently calculate the number of steps the algorithm takes?

Suppose that $a = mb + k$, where $0 \leq k < b$. Then the algorithm will take $m$ steps to reach $k,b$. I'll let you figure out how to use this in combination with the efficient GCD algorithm to efficiently calculate the number of steps your algorithm takes.