Most mind-blowing program for your favorite calculator
|
07-01-2022, 06:35 AM
Post: #20
|
|||
|
|||
RE: Most mind-blowing program for your favorite calculator
(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. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)