gcds

This crate implements several algorithms for finding the greatest common divisor of two single-precision numbers.

The greatest common divisor $\gcd(u,v)$ of two integers $u$ and $v$, not both zero, is the largest integer that evenly divides them both. This definition does not apply when $u$ and $v$ are both zero, since every number divides zero; for convenience, all the algorithms adhere to the convention that $\gcd(0,0)=0$.

This crate is by no means a complete catalog of gcd subroutines, but it does provide implementations of many of the most significant and most efficient methods that are currently known. Included, for example, are:

• euclid: The modern version of the Euclidean algorithm, as described in Algorithm 4.5.2A of The Art of Computer Programming.
• binary_stein: The binary gcd algorithm of J. Stein ["Computational Problems Associated with Racah Algebra," J. Comp. Phys. 1 (1967), 397--405].
• binary_bonzini: an optimized variant of the binary gcd algorithm proposed by P. Bonzini, and studied by D. Lemire ["Greatest common divisor, the extended Euclidean algorithm, and speed!" (April 2024)].
• binary_brent: an alternative formulation of the binary gcd algorithm proposed by R. P. Brent ["Further analysis of the Binary Euclidean algorithm," Technical Report PRG TR-7--99 (Oxford Univ. Computing Laboratory, 1999), Section 5].
• binary_brent_kung: a variant of the binary gcd algorithm suitable for implementation on a systolic array [R. P. Brent and H. T. Kung, IEEE Symposium on Computer Arithmetic 7 (1985), 118--125].
• harris: a cross between Euclid's algorithm and the binary gcd algorithm proposed by V. C. Harris [The Fibonacci Quarterly 8 (1970), 102--103].

Each subroutine is programmed in a somewhat literate style, and includes a short proof of correctness.

License

MIT © Hugo Sanz González