2
$\begingroup$

The Euclidean algorithm computes the $\gcd$ of two integers with the recursive formula

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

and takes at worst $\log_\varphi(\min(a,b))$ steps, where $\varphi$ is the golden ratio.

What if instead one used

$$\gcd(a,b)=\gcd(b,b-(a\bmod b))$$

whenever $a\bmod b$ was greater than $b/2$?

It is easy to see this will take at worst no more than $\log_2(\min(a,b))$ steps since this ensures the second argument is at most half of the first argument, but what is the exact worst case constant coeefficient?

The only sequence of pairs of integers I've managed to get the exact behavior of are consecutive Fibonacci numbers, in which case this modified algorithm runs twice as fast as the usual, which is faster than the $\log_2$ bound.

Here is a program displaying the values on each step of the standard Euclidean algorithm and the above modification.

$\endgroup$
6
  • $\begingroup$ This algorithm is already kind of "low level" enough that it might be worth thinking about how much complexity is involved in calculating this minimum at each iteration. In most modern CPUs, this will probably cost a significant number of cycles if you're trying to optimise your implementation. $\endgroup$ – Izaak van Dongen Jun 26 '20 at 0:23
  • 1
    $\begingroup$ The intention is to minimize the amount of modulo operations performed, since modulo operations are generally much more computationally expensive than operations like addition, subtraction, or comparisons. $\endgroup$ – Simply Beautiful Art Jun 26 '20 at 0:27
  • 1
    $\begingroup$ I believe this is known as the "smallest absolute remainder" version of the Euclidean algorithm, you might find something by searching for some term like that. $\endgroup$ – Gerry Myerson Jun 26 '20 at 1:46
  • $\begingroup$ @GerryMyerson Interesting, Wikipedia claims that it has the least amount of steps out of any version of Euclid's algorithm? $\endgroup$ – Simply Beautiful Art Jun 26 '20 at 1:53
  • $\begingroup$ That's not too surprising, since you're taking the smallest possible remainder at each stage. There's an analysis of Euclid's Algorithm and some variants in Knuth, Seminumerical Algorithms, well worth a look. $\endgroup$ – Gerry Myerson Jun 26 '20 at 1:58
1
$\begingroup$

Since you keep $b$ less than $a/2$, each time the quotient is at least $2$ (except the first step).

So instead of the Fibonacci, you need a sequence defined by $A_n=2A_{n-1}+A_{n-2}$ with $A_0=0,A_1=1$. Then this modified algorithm need $n$ steps to compute $\gcd(A_n+A_{n-1},A_n)$ (not $\gcd(A_n,A_{n-1})$, because we should let the first quotient be $1$).

Like the proof of $F_n$ makes the original algorithm run the most steps, also we can proof $A_n$ makes this modified algorithm runs the most steps: by induction on $n$ that if $a>2b$ and $\gcd(a,b)$ need $n$ steps, then $a\geq A_{n+1},b\geq A_n$:

$n=0$ is clearly true. If $n>0$, By induction hypothesis, $b\geq A_n$. There are two cases for $A$: 1) $a\bmod b\geq b/2$, then $a\geq 2A_n+A_n/2\geq A_{n+1}$. 2) $a\bmod b<b/2$, then $a-2b\geq a\bmod b\geq A_{n-1}$, so $a\geq A_{n+1}$.

Cause $A_n\sim c(1+\sqrt2)^n$, the algorithm runs in $\log_{1+\sqrt2}(\min(a,b))$ time.

$\endgroup$
2
  • $\begingroup$ I get $(A_{10},A_{11})=(341,683)$, of which Euclid's algorithm computes $\gcd(A_{10}+A_{11},A_{11})$ in only 2 or 3 iterations. In fact it would seem to be the case that this is true for any $n$. $\endgroup$ – Simply Beautiful Art Jun 26 '20 at 12:06
  • $\begingroup$ Whoops, I accidentally used $A_n=A_{n-1}+2A_{n-2}$ instead. This seems to work, but the use of $A_n+A_{n-1}$ seems unnecessary. $\endgroup$ – Simply Beautiful Art Jun 26 '20 at 14:45

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.