Binary GCD

https://en.algorithmica.org/hpc/analyzing-performance/gcd/

by sereja • 5 years ago

17 2 5 years ago

en.algorithmica.org

nullc• 5 years ago

The binary GCD has inferior performance to other approaches for big numbers because those min() comparisons require that you had to update the entire numbers at each step.

I submitted a writeup on the safegcd algorithm used by libsecp256k1 a while back, but it got the HN zomg-bitcoin-related quick flagging: https://github.com/bitcoin-core/secp256k1/blob/master/doc/sa...

Safegcd-like functions requires somewhat more iterations but most of the iterations need to only operate on the least significant bits of the numbers, which makes them faster in practice.

For safegcd-ish functions proving a hard upper bound on the number of require iterations is non-trivial. But it's useful to prove the bound in order to make constant time versions. Here is a writeup on our techniques for proving the upper bounds: https://github.com/sipa/safegcd-bounds#bounds-on-divsteps-it...

kamray23• 5 years ago

So, as with nearly everything, it's application-specific which one you should choose. Grand.

Binary GCD

Related Stories