Most mind-blowing program for your favorite calculator

[Thomas Klemm]

(07-01-2022 05:38 AM)pauln Wrote:  The non-mod version of Euclid's algorithm is prohibitively slow

Well, it depends.
The worst case for the mod version is using two consecutive Fibonacci numbers.
E.g. 144 and 89.

\(
\begin{matrix}
a & b & n = \lfloor a \div b \rfloor & r = a - n \times b \\
144 & 89 & 1 & 55 \\
89 & 55 & 1 & 34 \\
55 & 34 & 1 & 21 \\
34 & 21 & 1 & 13 \\
21 & 13 & 1 & 8 \\
13 & 8 & 1 & 5 \\
8 & 5 & 1 & 3 \\
5 & 3 & 1 & 2 \\
3 & 2 & 1 & 1 \\
2 & 1 & 2 & 0 \\
\end{matrix}
\)

The non-mod version uses the same amount of steps but avoids division and multiplication.
Thus it is even faster.

However with something like 9,999,999,999 and 2 I totally agree.
But in such cases you may calculate the remainder once manually to bring both numbers into the same ballpark.
Of course you could still end up with a pathological case like 9,999,999,999 and 99,998 where that has to be repeated.
But that is usually not the case.