Re:GCD and the magic of subtraction
by edflsafoiewq on Tuesday August 25, 2020 @01:41AM
(#24268402)
This can be seen as a "sped up" version of subtraction, since a%b = a-bk = a-b-b-...-b for some k.
If you were doing it by hand you would always take (the larger)%(the smaller). You use modulo-then-swap instead, which is interesting. If a<b, then the modulo is wasted, but the swap ensures the next modulo won't be.
If you were doing it by hand you would always take (the larger)%(the smaller). You use modulo-then-swap instead, which is interesting. If a<b, then the modulo is wasted, but the swap ensures the next modulo won't be.