Crate 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$.

Functions

binary_bonzini

Computes the greatest common divisor of $u$ and $v$ using 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

Computes the greatest common divisor of $u$ and $v$ using 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

Computes the greatest common divisor of $u$ and $v$ using the systolic variant of the binary gcd algorithm by R. P. Brent and H. T. Kung [IEEE Symposium on Computer Arithmetic 7 (1985), 118–125].

binary_stein

Computes the greatest common divisor of $u$ and $v$ using the binary gcd algorithm of J. Stein [“Computational Problems Associated with Racah Algebra,” J. Comp. Phys. 1 (1967), 397–405].

euclid

Computes the greatest common divisor of $u$ and $v$ using the modern version of the Euclidean algorithm, as described in Algorithm 4.5.2A of TAOCP.

harris

Computes the greatest common divisor of $u$ and $v$ using a cross between Euclid’s algorithm and the binary gcd algorithm proposed by V. C. Harris [The Fibonacci Quarterly 8 (1970), 102–103].