| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Greatest common divisor"
(Moving to new subcategory) |
(Copying error-checking method from forums) |
||
| Line 16: | Line 16: | ||
There are faster methods, especially when number of thousands or millions of digits are used, as in [[GIMPS]], but they are much more complex than the one presented above. | There are faster methods, especially when number of thousands or millions of digits are used, as in [[GIMPS]], but they are much more complex than the one presented above. | ||
| + | |||
| + | ==Error checking method== | ||
| + | This method may be used to error-check a GCD computation. It was suggested by [[Robert Gerbicz]] in [https://www.mersenneforum.org/showpost.php?p=639194&postcount=43 a MersenneForum post], and may possibly be found elsewhere as well. | ||
| + | |||
| + | To calculate <math>gcd(x,y)</math>: | ||
| + | # Take a random 64-bit prime: <math>q</math>. | ||
| + | # Calculate <math>v=gcd(q*x,q*y)</math>. | ||
| + | # If <math>q</math> does not divide <math>v</math>, then there was an error, otherwise <math>gcd(x,y)=v/q</math> (with large probability). | ||
==External links== | ==External links== | ||
*[https://en.wikipedia.org/wiki/Greatest_common_divisor Wikipedia] | *[https://en.wikipedia.org/wiki/Greatest_common_divisor Wikipedia] | ||
[[Category:Functions]] | [[Category:Functions]] | ||
Revision as of 18:32, 27 September 2023
The Greatest common divisor (gcd) of two numbers, commonly expressed by [math]\displaystyle{ gcd(a, b) }[/math], where [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are positive integers, is the maximum number that divides both [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math].
We can also define [math]\displaystyle{ gcd(a, 0) = a }[/math] and [math]\displaystyle{ gcd(a, b) = gcd(|a|, |b|) }[/math] thus defining the operations for all integers.
When the greatest common divisor is 1, both numbers are coprime or relatively prime. This does not mean that either of these numbers are prime.
Although the GCD can be readily computed if the prime factors of both numbers are known, in the context of this wiki the numbers are not factored in advance and the GCD helps find a factor of these numbers, so an alternate method is required.
Fortunately Euclid discovered such an algorithm more than 2000 years ago. Expressed in modern notation the algorithm is:
- If [math]\displaystyle{ b = 0 }[/math], terminate the algorithm with [math]\displaystyle{ a = 0 }[/math] as the answer.
- Set a temporary variable [math]\displaystyle{ r }[/math] to [math]\displaystyle{ a\,\mathrm{mod}\,b }[/math].
- Set the variable [math]\displaystyle{ a }[/math] to [math]\displaystyle{ b }[/math].
- Set the variable [math]\displaystyle{ b }[/math] to [math]\displaystyle{ r }[/math].
- Go back to step 1.
There are faster methods, especially when number of thousands or millions of digits are used, as in GIMPS, but they are much more complex than the one presented above.
Error checking method
This method may be used to error-check a GCD computation. It was suggested by Robert Gerbicz in a MersenneForum post, and may possibly be found elsewhere as well.
To calculate [math]\displaystyle{ gcd(x,y) }[/math]:
- Take a random 64-bit prime: [math]\displaystyle{ q }[/math].
- Calculate [math]\displaystyle{ v=gcd(q*x,q*y) }[/math].
- If [math]\displaystyle{ q }[/math] does not divide [math]\displaystyle{ v }[/math], then there was an error, otherwise [math]\displaystyle{ gcd(x,y)=v/q }[/math] (with large probability).
