Common · Knowledge
Binary GCD algorithm
Algorithm that computes the greatest common divisor of two integers using only arithmetic shifts, comparisons, and subtraction
The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor (GCD) of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction.
From Wikipedia
The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor (GCD) of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Although the algorithm in its contemporary form was first published by the physicist and programmer Josef Stein in 1967, it was known by the 2nd century BCE, in ancient China.
Text: Wikipédia, CC BY-SA 4.0. · Image: Cmglee (CC BY-SA 3.0) ·
Related cards
-
★★★
Euclidean algorithm
Algorithm for computing greatest common divisors
-
★★★
Binary-coded decimal
Class of binary encodings of decimal numbers where each decimal digit is represented by a fixed number of bits, usually four or eight. Special bit patterns are sometimes used for a sign or for other indications
-
★★★
Euclidean division
Division with remainder of integers
-
★★
Hungarian algorithm
Combinatorial optimization algorithm for the assignment problem
-
P★★
Proper generalized decomposition
Numerical method for solving boundary value problems
-
★★★
Bézout's identity
Formula relating two numbers and their greatest common divisor