nor's blog

A practical theoretically faster variant of the Euclidean GCD algorithm
By nor, 6 months ago, In English

https://nor-blog.codeberg.page/posts/2023-11-28-faster-euclidean-gcd/

  • Vote: I like it
  • +88
  • Vote: I do not like it

»
6 months ago, # |
← Rev. 2   Vote: I like it +93 Vote: I do not like it

I've come across this a few years ago (and proposed this idea to a local team competition). The keywords here are "least absolute remainder Euclidean algorithm" and this strategy is proven to be optimal among Euclidean-type algorithms ([1] mentions it, but I couldn't find Kronecker's original proof).

The worst-case inputs for this algorithm are Pell numbers, given by a recurrence $$$A_n = 2A_{n-1} + A_{n-2}$$$. They are asymptotically equal to $$$(1+\sqrt{2})^n \approxeq 2.4142^n$$$, which means that the number of iterations is about $$$\log_{2.4142} C$$$ (also briefly mentioned in [2]). The proof should be similar to the normal Fibonacci bound; I found one on ProofWiki, which looks okay to me at first glance.

[1]: A. W. Goodman & W. M. Zaring (1952) Euclid's Algorithm and the Least-Remainder Algorithm

[2]: Jeffrey Shallit (1990), On the worst case of three algorithms for computing the Jacobi symbol

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Wow, thanks for the references! Didn't expect it to be optimal, or even just better than the standard algorithm in all cases. I'll try to find Kronecker's proof on my own as well, and will update here if I succeed.

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So I dug up a couple of references — and Kronecker's original proof is presented in [3].

    The summary of the proof is as follows:

    1. Firstly show that for integers $$$a, b$$$ with $$$0 < 2a \le b$$$, the number of iterations by the least remainder algorithm on $$$b, a$$$ is at most the number of iterations by the least remainder algorithm on $$$b, b - a$$$. This can be shown using strong induction (which is admittedly quite tricky), with cases on $$$b \ge 3a$$$, $$$b < 5a/2$$$ and $$$5a/2 \le b < 3a$$$, and reasoning about the next few steps.
    2. Now the above claim can be used to show the desired claim, via strong induction again. This is simple because after one step, either we have the same pair of numbers, or one where the setup of the previous claim arises.

    [3]: Uspensky & Heaslet, Elementary Number Theory (chapter 3, section 2-4)

    → Reply