Binary GCD algorithm
The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor 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 Israeli physicist and programmer Josef Stein in 1967, it may have been known by the 2nd century BCE, in ancient China.
- Comment
- enThe binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor 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 Israeli physicist and programmer Josef Stein in 1967, it may have been known by the 2nd century BCE, in ancient China.
- Depiction
- Has abstract
- enThe binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor 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 Israeli physicist and programmer Josef Stein in 1967, it may have been known by the 2nd century BCE, in ancient China.
- Hypernym
- Algorithm
- Is primary topic of
- Binary GCD algorithm
- Label
- enBinary GCD algorithm
- Link from a Wikipage to an external page
- www.cut-the-knot.org/blue/binary.shtml
- xlinux.nist.gov/dads/HTML/binaryGCD.html
- users.info.unicaen.fr/~brigitte/Publications/bin-gcd.ps
- web.archive.org/web/20110513012901/http:/users.info.unicaen.fr/~brigitte/Publications/bin-gcd.ps
- books.google.com/books%3Fid=hXGr-9l1DXcC
- wwwmaths.anu.edu.au/~brent/pub/pub037.html
- Link from a Wikipage to another Wikipage
- Arbitrary-precision arithmetic
- Arithmetic shift
- Asymptotic notation
- Bézout coefficients
- Big-O notation
- Branch (computer science)
- Category:Articles with example C code
- Category:Number theoretic algorithms
- Conditional moves
- Continued fraction
- Count trailing zeros
- Cut-the-knot
- Dynamical system
- Eisenstein integers
- Euclidean algorithm
- Extended Euclidean algorithm
- File:Binary GCD algorithm visualisation.svg
- Functional analysis
- Gaussian integers
- Graduate Texts in Mathematics
- Greatest common divisor
- Han dynasty
- Invariant measure
- Iteration
- Least common multiple
- Lehmer's GCD algorithm
- Number fields
- Recursion (computer science)
- Richard Brent (scientist)
- Ring of integers
- Rust (programming language)
- Schönhage–Strassen algorithm
- Springer-Verlag
- The Art of Computer Programming
- The Nine Chapters on the Mathematical Art
- Transfer operator
- Trial division
- Unique factorization domain
- Word (computer architecture)
- SameAs
- 4ofyS
- Algorithme binaire de calcul du PGCD
- Binary GCD algorithm
- m.03wryx
- Q622328
- Steinscher Algorithmus
- Бинарни НЗД алгоритам
- Бинарный алгоритм вычисления НОД
- Бінарны алгарытм вылічэння НАД
- Двійковий алгоритм обчислення найбільшого спільного дільника
- الخوارزمية الثنائية لحساب القاسم المشترك الأكبر
- الگوریتم جیسیدی دودویی
- 이진 최대공약수 알고리즘
- Source
- The Nine Chapters on the Mathematical Art
- Subject
- Category:Articles with example C code
- Category:Number theoretic algorithms
- Text
- enIf possible halve it; otherwise, take the denominator and the numerator, subtract the lesser from the greater, and do that alternately to make them the same. Reduce by the same number.
- Thumbnail
- Title
- enFangtian – Land surveying
- WasDerivedFrom
- Binary GCD algorithm?oldid=1116283576&ns=0
- WikiPageLength
- 16397
- Wikipage page ID
- 985410
- Wikipage revision ID
- 1116283576
- WikiPageUsesTemplate
- Template:Citation needed
- Template:Cite book
- Template:Cite journal
- Template:Number theoretic algorithms
- Template:Portal
- Template:Quote
- Template:R
- Template:Use dmy dates
