Binary GCD algorithm - Revision history

Frap: Add category

2025-01-28T13:05:04Z

Add category

← Previous revision		Revision as of 13:05, 28 January 2025
Line 207:		Line 207:
	{{DEFAULTSORT:Binary Gcd Algorithm}}		{{DEFAULTSORT:Binary Gcd Algorithm}}
	[[Category:Number theoretic algorithms]]		[[Category:Number theoretic algorithms]]
	[[Category:Articles with example C code]]		[[Category:Articles with example Rust code]]

Dyspophyr: /* Further reading */ link -> simple continued fraction

2024-11-11T16:14:32Z

Further reading: link -> simple continued fraction

← Previous revision		Revision as of 16:14, 11 November 2024
Line 187:		Line 187:
	\|isbn= 0-387-55640-0\|publisher=[[Springer-Verlag]]\|series=[[Graduate Texts in Mathematics]]\|volume=138		\|isbn= 0-387-55640-0\|publisher=[[Springer-Verlag]]\|series=[[Graduate Texts in Mathematics]]\|volume=138
	\|url= https://books.google.com/books?id=hXGr-9l1DXcC}}		\|url= https://books.google.com/books?id=hXGr-9l1DXcC}}
	Covers a variety of topics, including the extended binary GCD algorithm which outputs [[Bézout coefficients]], efficient handling of multi-precision integers using a variant of [[Lehmer's GCD algorithm]], and the relationship between GCD and [[continued fraction]] ~~expansions~~ of real numbers.		Covers a variety of topics, including the extended binary GCD algorithm which outputs [[Bézout coefficients]], efficient handling of multi-precision integers using a variant of [[Lehmer's GCD algorithm]], and the relationship between GCD and [[simple continued fraction\|continued fraction expansion]]s of real numbers.

	* {{cite journal\|last=Vallée \|first=Brigitte \| author-link=Brigitte Vallée		* {{cite journal\|last=Vallée \|first=Brigitte \| author-link=Brigitte Vallée

Bubba73: /* Extensions */

2024-10-17T06:56:36Z

Extensions

← Previous revision		Revision as of 06:56, 17 October 2024
Line 96:		Line 96:
	==Extensions==		==Extensions==

	The binary GCD algorithm can be extended in several ways, either to output additional information, deal with [[Arbitrary-precision arithmetic\|arbitrarily-large integers]] more efficiently, or to compute GCDs in domains other than the integers.		The binary GCD algorithm can be extended in several ways, either to output additional information, deal with [[Arbitrary-precision arithmetic\|arbitrarily large integers]] more efficiently, or to compute GCDs in domains other than the integers.

	The ''extended binary GCD'' algorithm, analogous to the [[extended Euclidean algorithm]], fits in the first kind of extension, as it provides the [[Bézout coefficients]] in addition to the GCD: integers <math>a</math> and <math>b</math> such that <math>a\cdot{}u + b\cdot{}v = \gcd(u, v)</math>.<ref name="egcd-knuth"/><ref name="egcd-applied-crypto"/><ref name="egcd-cohen"/>		The ''extended binary GCD'' algorithm, analogous to the [[extended Euclidean algorithm]], fits in the first kind of extension, as it provides the [[Bézout coefficients]] in addition to the GCD: integers <math>a</math> and <math>b</math> such that <math>a\cdot{}u + b\cdot{}v = \gcd(u, v)</math>.<ref name="egcd-knuth"/><ref name="egcd-applied-crypto"/><ref name="egcd-cohen"/>

Bubba73: /* Complexity */ no hyphen after -ly adverbs

2024-10-17T06:55:37Z

Complexity: no hyphen after -ly adverbs

← Previous revision		Revision as of 06:55, 17 October 2024
Line 86:		Line 86:
	[[Big O notation\|Asymptotically]], the algorithm requires <math>O(n)</math> steps, where <math>n</math> is the number of bits in the larger of the two numbers, as every two steps reduce at least one of the operands by at least a factor of <math>2</math>. Each step involves only a few arithmetic operations (<math>O(1)</math> with a small constant); when working with [[Word (computer architecture)\|word-sized]] numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of <math>n</math>, i.e. <math>\log_{2}(\max(u, v))</math>.		[[Big O notation\|Asymptotically]], the algorithm requires <math>O(n)</math> steps, where <math>n</math> is the number of bits in the larger of the two numbers, as every two steps reduce at least one of the operands by at least a factor of <math>2</math>. Each step involves only a few arithmetic operations (<math>O(1)</math> with a small constant); when working with [[Word (computer architecture)\|word-sized]] numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of <math>n</math>, i.e. <math>\log_{2}(\max(u, v))</math>.

	For arbitrarily-large numbers, the [[asymptotic notation\|asymptotic complexity]] of this algorithm is <math>O(n^2)</math>,<ref name="gmplib"/> as each arithmetic operation (subtract and shift) involves a linear number of machine operations (one per word in the numbers' binary representation).		For arbitrarily large numbers, the [[asymptotic notation\|asymptotic complexity]] of this algorithm is <math>O(n^2)</math>,<ref name="gmplib"/> as each arithmetic operation (subtract and shift) involves a linear number of machine operations (one per word in the numbers' binary representation).
	If the numbers can be represented in the machine's memory, ''i.e.'' each number's ''size'' can be represented by a single machine word, this bound is reduced to:		If the numbers can be represented in the machine's memory, ''i.e.'' each number's ''size'' can be represented by a single machine word, this bound is reduced to:
	<math display="block">		<math display="block">

Bubba73: Changing short description from "Algorithm in mathematics" to "Algorithm for computing the greatest common divisor"

2024-10-17T06:53:19Z

Changing short description from "Algorithm in mathematics" to "Algorithm for computing the greatest common divisor"

← Previous revision		Revision as of 06:53, 17 October 2024
Line 1:		Line 1:
	{{Short description\|Algorithm in ~~mathematics~~}}		{{Short description\|Algorithm for computing the greatest common divisor}}
	{{Use dmy dates\|date=April 2022}}		{{Use dmy dates\|date=April 2022}}
	[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]		[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]

LR.127: Adding local short description: "Algorithm in mathematics", overriding Wikidata description "algorithm that computes the greatest common divisor of two integers using only arithmetic shifts, comparisons, and subtraction"

2024-10-02T00:55:14Z

Adding local short description: "Algorithm in mathematics", overriding Wikidata description "algorithm that computes the greatest common divisor of two integers using only arithmetic shifts, comparisons, and subtraction"

← Previous revision		Revision as of 00:55, 2 October 2024
Line 1:		Line 1:
			{{Short description\|Algorithm in mathematics}}
	{{Use dmy dates\|date=April 2022}}		{{Use dmy dates\|date=April 2022}}
	[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]		[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]

AstonishingTunesAdmirer: /* Implementation */ this template is for use in discussions

2024-09-08T14:01:22Z

Implementation: this template is for use in discussions

← Previous revision		Revision as of 14:01, 8 September 2024
Line 73:		Line 73:
	</syntaxhighlight>		</syntaxhighlight>

	~~{{A note}}~~ The implementation above accepts ''unsigned'' (non-negative) integers; given that <math>\gcd(u, v) = \gcd(\pm{}u, \pm{}v)</math>, the signed case can be handled as follows:		'''Note''': The implementation above accepts ''unsigned'' (non-negative) integers; given that <math>\gcd(u, v) = \gcd(\pm{}u, \pm{}v)</math>, the signed case can be handled as follows:
	<syntaxhighlight lang="rust">		<syntaxhighlight lang="rust">
	/// Computes the GCD of two signed 64-bit integers		/// Computes the GCD of two signed 64-bit integers

174.89.113.20 at 02:27, 26 July 2024

2024-07-26T02:27:38Z

← Previous revision		Revision as of 02:27, 26 July 2024
Line 4:		Line 4:
	The '''binary GCD algorithm''', also known as '''Stein's algorithm''' or the '''binary Euclidean algorithm''',{{r\|brenta\|brentb}} 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 shift]]s, comparisons, and subtraction.		The '''binary GCD algorithm''', also known as '''Stein's algorithm''' or the '''binary Euclidean algorithm''',{{r\|brenta\|brentb}} 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 shift]]s, comparisons, and subtraction.

	Although the algorithm in its contemporary form was first published by the ~~Israeli~~ physicist and programmer Josef Stein in 1967,<ref name="Stein"/> it ~~may have been~~ known by the 2nd century BCE, in ancient China.{{r\|Knuth98}}		Although the algorithm in its contemporary form was first published by the physicist and programmer Josef Stein in 1967,<ref name="Stein"/> it was known by the 2nd century BCE, in ancient China.{{r\|Knuth98}}

	==Algorithm==		==Algorithm==

HTinC23: changed gcd and max to upright (MOS:MATH#Multi-letter names)

2024-06-29T11:20:36Z

changed gcd and max to upright (MOS:MATH#Multi-letter names)

← Previous revision		Revision as of 11:20, 29 June 2024
Line 10:		Line 10:
	The algorithm finds the GCD of two nonnegative numbers <math>u</math> and <math>v</math> by repeatedly applying these identities:		The algorithm finds the GCD of two nonnegative numbers <math>u</math> and <math>v</math> by repeatedly applying these identities:

	# <math>gcd(u, 0) = u</math>: everything divides zero, and <math>u</math> is the largest number that divides <math>u</math>.		# <math>\gcd(u, 0) = u</math>: everything divides zero, and <math>u</math> is the largest number that divides <math>u</math>.
	# <math>gcd(2u, 2v) = 2 \cdot gcd(u, v)</math>: <math>2</math> is a common divisor.		# <math>\gcd(2u, 2v) = 2 \cdot \gcd(u, v)</math>: <math>2</math> is a common divisor.
	# <math>gcd(u, 2v) = gcd(u, v)</math> if <math>u</math> is odd: <math>2</math> is then not a common divisor.		# <math>\gcd(u, 2v) = \gcd(u, v)</math> if <math>u</math> is odd: <math>2</math> is then not a common divisor.
	# <math>gcd(u, v) = gcd(u, v - u)</math> if <math>u, v</math> odd and <math>u \leq v</math>.		# <math>\gcd(u, v) = \gcd(u, v - u)</math> if <math>u, v</math> odd and <math>u \leq v</math>.

	As GCD is commutative (<math>gcd(u, v) = gcd(v, u)</math>), those identities still apply if the operands are swapped: <math>gcd(0, v) = v</math>, <math>gcd(2u, v) = gcd(u, v)</math> if <math>v</math> is odd, etc.		As GCD is commutative (<math>\gcd(u, v) = \gcd(v, u)</math>), those identities still apply if the operands are swapped: <math>\gcd(0, v) = v</math>, <math>\gcd(2u, v) = \gcd(u, v)</math> if <math>v</math> is odd, etc.

	==Implementation==		==Implementation==
Line 73:		Line 73:
	</syntaxhighlight>		</syntaxhighlight>

	{{A note}} The implementation above accepts ''unsigned'' (non-negative) integers; given that <math>gcd(u, v) = gcd(\pm{}u, \pm{}v)</math>, the signed case can be handled as follows:		{{A note}} The implementation above accepts ''unsigned'' (non-negative) integers; given that <math>\gcd(u, v) = \gcd(\pm{}u, \pm{}v)</math>, the signed case can be handled as follows:
	<syntaxhighlight lang="rust">		<syntaxhighlight lang="rust">
	/// Computes the GCD of two signed 64-bit integers		/// Computes the GCD of two signed 64-bit integers
Line 83:		Line 83:

	==Complexity==		==Complexity==
	[[Big O notation\|Asymptotically]], the algorithm requires <math>O(n)</math> steps, where <math>n</math> is the number of bits in the larger of the two numbers, as every two steps reduce at least one of the operands by at least a factor of <math>2</math>. Each step involves only a few arithmetic operations (<math>O(1)</math> with a small constant); when working with [[Word (computer architecture)\|word-sized]] numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of <math>n</math>, i.e. <math>\log_{2}(max(u, v))</math>.		[[Big O notation\|Asymptotically]], the algorithm requires <math>O(n)</math> steps, where <math>n</math> is the number of bits in the larger of the two numbers, as every two steps reduce at least one of the operands by at least a factor of <math>2</math>. Each step involves only a few arithmetic operations (<math>O(1)</math> with a small constant); when working with [[Word (computer architecture)\|word-sized]] numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of <math>n</math>, i.e. <math>\log_{2}(\max(u, v))</math>.

	For arbitrarily-large numbers, the [[asymptotic notation\|asymptotic complexity]] of this algorithm is <math>O(n^2)</math>,<ref name="gmplib"/> as each arithmetic operation (subtract and shift) involves a linear number of machine operations (one per word in the numbers' binary representation).		For arbitrarily-large numbers, the [[asymptotic notation\|asymptotic complexity]] of this algorithm is <math>O(n^2)</math>,<ref name="gmplib"/> as each arithmetic operation (subtract and shift) involves a linear number of machine operations (one per word in the numbers' binary representation).
Line 97:		Line 97:
	The binary GCD algorithm can be extended in several ways, either to output additional information, deal with [[Arbitrary-precision arithmetic\|arbitrarily-large integers]] more efficiently, or to compute GCDs in domains other than the integers.		The binary GCD algorithm can be extended in several ways, either to output additional information, deal with [[Arbitrary-precision arithmetic\|arbitrarily-large integers]] more efficiently, or to compute GCDs in domains other than the integers.

	The ''extended binary GCD'' algorithm, analogous to the [[extended Euclidean algorithm]], fits in the first kind of extension, as it provides the [[Bézout coefficients]] in addition to the GCD: integers <math>a</math> and <math>b</math> such that <math>a\cdot{}u + b\cdot{}v = gcd(u, v)</math>.<ref name="egcd-knuth"/><ref name="egcd-applied-crypto"/><ref name="egcd-cohen"/>		The ''extended binary GCD'' algorithm, analogous to the [[extended Euclidean algorithm]], fits in the first kind of extension, as it provides the [[Bézout coefficients]] in addition to the GCD: integers <math>a</math> and <math>b</math> such that <math>a\cdot{}u + b\cdot{}v = \gcd(u, v)</math>.<ref name="egcd-knuth"/><ref name="egcd-applied-crypto"/><ref name="egcd-cohen"/>

	In the case of large integers, the best asymptotic complexity is <math>O(M(n) \log n)</math>, with <math>M(n)</math> the cost of <math>n</math>-bit multiplication; this is near-linear and vastly smaller than the binary GCD algorithm's <math>O(n^2)</math>, though concrete implementations only outperform older algorithms for numbers larger than about 64 kilobits (''i.e.'' greater than 8×10<sup>19265</sup>). This is achieved by extending the binary GCD algorithm using ideas from the [[Schönhage–Strassen algorithm]] for fast integer multiplication.<ref name="stehlé-zimmermann"/>		In the case of large integers, the best asymptotic complexity is <math>O(M(n) \log n)</math>, with <math>M(n)</math> the cost of <math>n</math>-bit multiplication; this is near-linear and vastly smaller than the binary GCD algorithm's <math>O(n^2)</math>, though concrete implementations only outperform older algorithms for numbers larger than about 64 kilobits (''i.e.'' greater than 8×10<sup>19265</sup>). This is achieved by extending the binary GCD algorithm using ideas from the [[Schönhage–Strassen algorithm]] for fast integer multiplication.<ref name="stehlé-zimmermann"/>

147.83.76.249 at 15:13, 4 April 2024

2024-04-04T15:13:06Z

← Previous revision		Revision as of 15:13, 4 April 2024
Line 10:		Line 10:
	The algorithm finds the GCD of two nonnegative numbers <math>u</math> and <math>v</math> by repeatedly applying these identities:		The algorithm finds the GCD of two nonnegative numbers <math>u</math> and <math>v</math> by repeatedly applying these identities:

	# <math>gcd(u, 0) = u</math>: everything divides zero, and <math>v</math> is the largest number that divides <math>v</math>.		# <math>gcd(u, 0) = u</math>: everything divides zero, and <math>u</math> is the largest number that divides <math>u</math>.
	# <math>gcd(2u, 2v) = 2 \cdot gcd(u, v)</math>: <math>2</math> is a common divisor.		# <math>gcd(2u, 2v) = 2 \cdot gcd(u, v)</math>: <math>2</math> is a common divisor.
	# <math>gcd(u, 2v) = gcd(u, v)</math> if <math>u</math> is odd: <math>2</math> is then not a common divisor.		# <math>gcd(u, 2v) = gcd(u, v)</math> if <math>u</math> is odd: <math>2</math> is then not a common divisor.

← Previous revision		Revision as of 06:53, 17 October 2024
Line 1:		Line 1:
	{{Short description\|Algorithm in ~~mathematics~~}}		{{Short description\|Algorithm for computing the greatest common divisor}}
	{{Use dmy dates\|date=April 2022}}		{{Use dmy dates\|date=April 2022}}
	[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]		[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]

← Previous revision		Revision as of 00:55, 2 October 2024
Line 1:		Line 1:
			{{Short description\|Algorithm in mathematics}}
	{{Use dmy dates\|date=April 2022}}		{{Use dmy dates\|date=April 2022}}
	[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]		[[File:binary_GCD_algorithm_visualisation.svg\|thumb\|upright=1.8\|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]