Tight time complexity for GCD

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

(prologue) Some time ago this crossed my mind, but I only recalled it now and I think it could be worth a small blog post. This is nothing big and rarely useful but nevertheless, I found it interesting so hopefully you will too (don't expect to find this enriching).

It is widely known that the time complexity to compute the GCD (greatest common divisor) of two integers a, b, using the euclidean algorithm, is $\text{[math]}$ .

Short proof

This bound is nice and all, but we can provide a slightly tighter bound to the algorithm:

$\text{[math]}$

We show this bound by adding a few sentences to the above proof: once the smaller element becomes 0, we know that the larger element becomes the resulting gcd. Therefor we can first bound by $\text{[math]}$ , and lastly notice that we can change the maximum to minimum, since after one step of the algorithm the current maximum is the previous minimum; min(a, b) = max(b, a % b) when a ≥ b.

This bound is of course negligible... for a single gcd computation. It turns out to be somewhat useful when used multiple times in a row. I'll explain with an example "problem":

(1) Given an array A of n integers in range [1, M], compute their greatest common divisor.

The solution is of course, we start with the initial answer G = A₀, and iterate over all the remaining elements, assigning to G the value $\text{[math]}$ . The known time complexity analysis gives us the bound of $\text{[math]}$ , for computing gcd n times over values of order M. The tighter analysis actually gives a bound that is asymptotically better: $\text{[math]}$ (for practical values of M, you can refer to this as $\text{[math]}$ ). Why is that so? again, we can determine the time complexity more carefully:

The iteration over the array gives us the factor of n, while the remaining is recieved from gcd computations, which we analyze now; Let the value G_i be equal to G after the i-th iteration, that is:

G₀ = A₀
$\text{[math]}$

On the i-th iteration, the gcd computation starts with 2 values G_i - 1, A_i, and results with G_i, so the time complexity of it is $\text{[math]}$ , which is worstcase $\text{[math]}$ , so we will assume it's the latter.

The total gcd iterations (differing by a constant factor) is:

$\text{[math]}$

And generally speaking, this analysis sometimes allows us to show that the solution is quicker by a factor of $\text{[math]}$ .

As a last note,

Rev.	By	When	Δ	Comment
en5	Noam527	2018-12-12 00:22:53	0	(published)
en4	Noam527	2018-12-12 00:22:15	946
en3	Noam527	2018-12-11 23:58:39	835	Tiny change: ' \log(G_i)$' -> ' \log(G_i) = \log(G_0) - \log(G_{n-1}) < \log(G_0) \leq \log M$.'
en2	Noam527	2018-12-11 23:40:12	1221	Tiny change: '\min(a, b)' -> '\min(a, b) = \max(b, a \, % \, b)$ when $a \geq b$.'
en1	Noam527	2018-12-11 23:21:21	1653	Initial revision (saved to drafts)

History