1
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.