# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
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
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.
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:
[3]: Uspensky & Heaslet, Elementary Number Theory (chapter 3, section 2-4)