|
What's this GCD lagorithm called ? --Taw |
|
What's this GCD algorithm called ? --Taw |
|
a=(a-b)>>1 |
|
a-=b a>>=1 |
|
b=(b-a)>>1 |
|
b-=a b>>=1 |
|
I don't know, but it is cool. Runtime is O(lg(n)); I wonder if it is faster than the ordinary division method? (I changed one line to make it a tiny bit simpler.) --AxelBoldt |
|
I don't know, but it is cool. Runtime is O(lg(n)); I wonder if it is faster than the ordinary division method? (I changed one line to make it a tiny bit simpler.) --AxelBoldt It's much faster on most hardware because it doesn't use these slow modulo divisions, only ultra-fast shifts and substractions. If we're simplifying, here's an additional simplification. --Taw |
![[Home]](wikipedia.png)