GCD and the magic of subtraction(plumsempy.com)
plumsempy.com
GCD and the magic of subtraction
https://plumsempy.com/2020/08/24/gcd-and-the-magic-of-subtraction/
50 comments
The problem efficiency wise is that modulo (and any other form of division) is really slow. Therefore a binary version of this algorithm exist that only do divison by 2, which is faster as it can be implemented by using a shift instruction.
This can be seen as a "sped up" version of subtraction, since a%b = a-bk = a-b-b-...-b for some k.
If you were doing it by hand you would always take (the larger)%(the smaller). You use modulo-then-swap instead, which is interesting. If a<b, then the modulo is wasted, but the swap ensures the next modulo won't be.
If you were doing it by hand you would always take (the larger)%(the smaller). You use modulo-then-swap instead, which is interesting. If a<b, then the modulo is wasted, but the swap ensures the next modulo won't be.
This is interesting. Thank you.
It's just the Euclidean Algorithm; you call it out specifically in the OP. (Though, um, you define it incorrectly.)
I'm not sure what you're looking for with this comment:
> If someone has a better explanation of why subtracting relatively prime numbers repeatedly will always result in one, please leave a comment or reach out and help me understand better.
So I'll go through the proof that the Euclidean algorithm works, and then I'll apply the same proof to a raw subtraction ("the Euclidean Algorithm, but slower").
Step 1: for any two integers a, b, the Division Algorithm tells us there is a unique pair of integers q, r ("quotient, remainder") such that a = qb + r and 0 <= r < |b|.
Step 2: We want to find the GCD of two arbitrary integers, which we will call a and b.
Step 3: We will show that, when a = qb + r, GCD(a,b) = GCD(b,r). More explicitly, we will show that, when these two propositions are true:
Step 5: Getting the easy one out of the way, P2 suffices to prove D1.
Step 6: We need to show that z|r. By P1, a = zm for some integer m, and by P2, b = zn for some integer n. Then we have:
Step 7: To show that the GCDs are equal, we must also show that if z|r and z|b, then z|a. This is easy:
-------
Now, to apply this to subtraction.
Step 1: Instead of a = qb + r, we have the simpler equation a - b = r.
Step 2: We wish to show that given these two assumptions:
Step 4: By P1, a = zm for some integer m, and by P2, b = zn for some integer n. Then:
(And in the other direction, when z|r, z|b, and a = b + r, then z|a.)
Step 5: We have now shown that GCD(a,b) = GCD(b,a-b). Iterating this process of subtracting the smaller quantity from the larger quantity will (1) necessarily form a decreasing sequence of "a" values, until r = 0; and (2) eventually yield GCD(a,b).
The GCD of two relatively prime numbers is, by definition, 1. That's why you're guaranteed to end up with (1, 0) when you apply this process to two relatively prime numbers.
(Note that since all integers evenly divide 0, GCD(a,0) = a for all a.)
I'm not sure what you're looking for with this comment:
> If someone has a better explanation of why subtracting relatively prime numbers repeatedly will always result in one, please leave a comment or reach out and help me understand better.
So I'll go through the proof that the Euclidean algorithm works, and then I'll apply the same proof to a raw subtraction ("the Euclidean Algorithm, but slower").
Step 1: for any two integers a, b, the Division Algorithm tells us there is a unique pair of integers q, r ("quotient, remainder") such that a = qb + r and 0 <= r < |b|.
Step 2: We want to find the GCD of two arbitrary integers, which we will call a and b.
Step 3: We will show that, when a = qb + r, GCD(a,b) = GCD(b,r). More explicitly, we will show that, when these two propositions are true:
P1. z|a (in words, there is some integer m for which a = zm)
P2. z|b
D1. z|b
D2. z|r
Step 5: Getting the easy one out of the way, P2 suffices to prove D1.
Step 6: We need to show that z|r. By P1, a = zm for some integer m, and by P2, b = zn for some integer n. Then we have:
a = qb + r
zm = qzn + r
r = zm - qzn = z(m-qn)
Step 7: To show that the GCDs are equal, we must also show that if z|r and z|b, then z|a. This is easy:
a = qb + r
a = qzm + zn = z(qm + n)
-------
Now, to apply this to subtraction.
Step 1: Instead of a = qb + r, we have the simpler equation a - b = r.
Step 2: We wish to show that given these two assumptions:
P1. z|a
P2. z|b
D1. z|b
D2. z|r
Step 4: By P1, a = zm for some integer m, and by P2, b = zn for some integer n. Then:
a - b = r
zm - zn = r
z(m - n) = r
(And in the other direction, when z|r, z|b, and a = b + r, then z|a.)
Step 5: We have now shown that GCD(a,b) = GCD(b,a-b). Iterating this process of subtracting the smaller quantity from the larger quantity will (1) necessarily form a decreasing sequence of "a" values, until r = 0; and (2) eventually yield GCD(a,b).
The GCD of two relatively prime numbers is, by definition, 1. That's why you're guaranteed to end up with (1, 0) when you apply this process to two relatively prime numbers.
(Note that since all integers evenly divide 0, GCD(a,0) = a for all a.)
Thank you very much for the proof. I can understand the proof in my analytical thoughts, but what I have a problem with is an intuition for it.
Of course it can be that I need to sit with it more, work with it more, connect more basic subjects to my intuition first to make it work. It can also be that if everyone waited for things to make intuitive sense we will fall back in science. Math is a great tool where it can take you places even when you don't possess the correct intuition if you just follow the rules.
But I have decided to try the intuition way nonetheless. My main problem is that, it was not immediately obvious to me that subtracting coprimes successively will always result in 1. It is still so strange to me. In comparison the fundamental theory of arithmetic is also strange but there is a good intuition behind it: any non prime number is a product of primes, because if it wasn't it would be prime itself!
Of course it can be that I need to sit with it more, work with it more, connect more basic subjects to my intuition first to make it work. It can also be that if everyone waited for things to make intuitive sense we will fall back in science. Math is a great tool where it can take you places even when you don't possess the correct intuition if you just follow the rules.
But I have decided to try the intuition way nonetheless. My main problem is that, it was not immediately obvious to me that subtracting coprimes successively will always result in 1. It is still so strange to me. In comparison the fundamental theory of arithmetic is also strange but there is a good intuition behind it: any non prime number is a product of primes, because if it wasn't it would be prime itself!
> I can understand the proof in my analytical thoughts, but what I have a problem with is an intuition for it.
The intuition is a lot easier, to my eyes, for the subtraction.
What the proof is telling you is that, if you start with a multiple of 3, and you subtract a multiple of 3, what remains will still be a multiple of 3. (And similarly for any other value of 3.) This is pretty intuitive.
And as long as a and b are positive and distinct, max(b, a-b) is strictly less than max(a, b), so the iterative process produces a strictly decreasing sequence (until you get a 0 -- 0 isn't positive).
So the intuition is in two or three parts:
#1. Subtracting like this can never eliminate the GCD of the original pair of integers. ("Subtract one multiple of 24 from another multiple of 24, and you'll still have a multiple of 24.")
#2. It can, and will, eliminate everything else.
#3. If the original pair of numbers is relatively prime, their GCD is 1, so 1 is what you'll get from this process.
The intuition is a lot easier, to my eyes, for the subtraction.
What the proof is telling you is that, if you start with a multiple of 3, and you subtract a multiple of 3, what remains will still be a multiple of 3. (And similarly for any other value of 3.) This is pretty intuitive.
And as long as a and b are positive and distinct, max(b, a-b) is strictly less than max(a, b), so the iterative process produces a strictly decreasing sequence (until you get a 0 -- 0 isn't positive).
So the intuition is in two or three parts:
#1. Subtracting like this can never eliminate the GCD of the original pair of integers. ("Subtract one multiple of 24 from another multiple of 24, and you'll still have a multiple of 24.")
#2. It can, and will, eliminate everything else.
#3. If the original pair of numbers is relatively prime, their GCD is 1, so 1 is what you'll get from this process.
This comment is more to satisfy an aspect of the proof I was personally uncomfortable with.
We can easily show that (1) the iterative subtraction process always preserves divisibility by the GCD, and (2) it eventually reaches 0. (It cannot reach a negative value because we always subtract the smaller number from the larger number.)
It's slightly trickier to show that the process achieves the GCD before it hits zero. Theoretically, it could go from a multiple of the GCD to zero without passing through the GCD itself. This felt like a hole in my proof.
It is not the case, however:
In order to achieve r = 0, we must have had a = b at that step. We know that all of our pairs (a, b) and (b, r), at every step of the process, share the same GCD. Thus, the GCD of the original pair of numbers is equal to the GCD of the values a and b for which r = a-b = 0. Since GCD(m,m) = m for all m, this a and b are both equal to the GCD of the original pair -- which means that the process achieved the GCD.
We can easily show that (1) the iterative subtraction process always preserves divisibility by the GCD, and (2) it eventually reaches 0. (It cannot reach a negative value because we always subtract the smaller number from the larger number.)
It's slightly trickier to show that the process achieves the GCD before it hits zero. Theoretically, it could go from a multiple of the GCD to zero without passing through the GCD itself. This felt like a hole in my proof.
It is not the case, however:
In order to achieve r = 0, we must have had a = b at that step. We know that all of our pairs (a, b) and (b, r), at every step of the process, share the same GCD. Thus, the GCD of the original pair of numbers is equal to the GCD of the values a and b for which r = a-b = 0. Since GCD(m,m) = m for all m, this a and b are both equal to the GCD of the original pair -- which means that the process achieved the GCD.
> In comparison the fundamental theory of arithmetic is also strange but there is a good intuition behind it: any non prime number is a product of primes, because if it wasn't it would be prime itself!
That's true, but it doesn't prove the fundamental theorem of arithmetic. You need to show that e.g. if p,q,r,s are four different primes, then pq does not equal rs.
(The important part of the theorem is that the prime factorization of an integer is unique.)
That's true, but it doesn't prove the fundamental theorem of arithmetic. You need to show that e.g. if p,q,r,s are four different primes, then pq does not equal rs.
(The important part of the theorem is that the prime factorization of an integer is unique.)
> (Note that since all integers evenly divide 0, GCD(a,0) = a for all a.)
Nonzero a, that is.
Nonzero a, that is.
GCD(0,0) exists in any commutative ring by definition (and is not unique) :)
d is a common divisor of a,b if there exists x,y such that dx = ay, and d is a GCD of a,b if all divisors c divide d. So there exist many such x where GCD(0,0) = x (including x = 0).
d is a common divisor of a,b if there exists x,y such that dx = ay, and d is a GCD of a,b if all divisors c divide d. So there exist many such x where GCD(0,0) = x (including x = 0).
If you define GCD this way then writing gcd(a, b) = c is an abuse of notation :)
> d is a common divisor of a,b if there exists x,y such that dx = ay
d = 9
a = 3
b = 537
x = 1
y = 3
dx = 9(1) = 9
ay = 3(3) = 9 = dx
It's not necessary that the set of numbers be coprime: {2,4} fed into Euclid's algorithm would proceed to reduce to {2,2} then {2,0} then yield {2}.
In general Euclid's algorithm is a special case of Buchberger's algorithm, q.v., if interested.
In general Euclid's algorithm is a special case of Buchberger's algorithm, q.v., if interested.
It is definitely not necessary. Because the gcd of 2 and 4 is 2, thus we have 2(1) and 2(2). 2 and 1 are coprime and thus will reduce down to 1, the common part left out is 2 and the uncommon part is 1, as always 1.
Thanks about the Buchberger intro I didn't know about that.
Thanks about the Buchberger intro I didn't know about that.
What's q.v?
Also, Buchberger is a special case of Knuth-Bendix completion :D
Also, Buchberger is a special case of Knuth-Bendix completion :D
> What's q.v?
"quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide .
"quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide .
So basically "see also" in Latin?
good point: "see" even by itself works, but i had lots of Latin so didn't think of it.
yep...fun stuff.
https://www.amazon.com/Ideals-Varieties-Algorithms-Computati...
covers much of this topic
https://www.amazon.com/Ideals-Varieties-Algorithms-Computati...
covers much of this topic
> If someone has a better explanation of why subtracting relatively prime numbers repeatedly will always result in one
I'm not sure about better, but I think I can explain it more simply.
Our subtraction is "a - b = c", where "a" and "b" have no factors in common. And the result is that "c" also has no factors in common with "b". Well, what if they did? What would it look like if "b" and "c" had a common factor?
Let's use the example of "b = 6", that was used in the article. 6 has two factors: 2 and 3, so let's see what happens if 2 is a factor of the resulting "c":
(slightly more mathy: we're looking at "a = b + c", where b = px and c = qx (x is the common factor), so we have "a = px + qx" yet we're claiming that "x" is not a factor of "a")
Anyway, since we're subtracting and always get a smaller number, and it's always a relative prime, we clearly must end up with 1.
I'm not sure about better, but I think I can explain it more simply.
Our subtraction is "a - b = c", where "a" and "b" have no factors in common. And the result is that "c" also has no factors in common with "b". Well, what if they did? What would it look like if "b" and "c" had a common factor?
Let's use the example of "b = 6", that was used in the article. 6 has two factors: 2 and 3, so let's see what happens if 2 is a factor of the resulting "c":
a - b = c
----------
8 - 6 = 2
10 - 6 = 4
12 - 6 = 6
14 - 6 = 8
a - b = c
----------
9 - 6 = 3
12 - 6 = 6
15 - 6 = 9
18 - 6 = 12
(slightly more mathy: we're looking at "a = b + c", where b = px and c = qx (x is the common factor), so we have "a = px + qx" yet we're claiming that "x" is not a factor of "a")
Anyway, since we're subtracting and always get a smaller number, and it's always a relative prime, we clearly must end up with 1.
yeah~ its clicking a bit more now, thank you. I am comfortable with the fact that the remainder is a coprime of a and b; but that corprimes have a definitive path to 1 is strange. Why now 0 or -1? or -2? it is not clear to me why it must always converge to 1.
Well, it can't hit zero because you'd need equal numbers for that, and they're not coprime ;)
It can't be negative because you cheat and always put "larger - smaller". See your own example: you go:
It can't be negative because you cheat and always put "larger - smaller". See your own example: you go:
13 - 7 = 6 -> 7 - 6 = 1
a - b = c -> b - c = d
6 - 1 = 5 -> 5 - 1 = 4
a - b = c -> c - b = d
A generalized version of the while loop was suggested by Edsger Dijkstra. This loop has more than one guard and terminates when all guards evaluate to false. With this construct the greatest common divisor can be calculated quite succinctly as
https://miasap.se/obnc/oberon-report.html#sec9.6
WHILE a < b DO
b := b - a
ELSIF a > b DO
a := a - b
END
https://miasap.se/obnc/oberon-report.html#sec9.6
Wouldn't that be `else: break` in every other language?
In most other languages it would be something like
while true do
if condition 1 do
statements 1
done
else if condition 2 do
statements 2
done
else do
break
done
doneOberon, however, is a purely structured language and has no goto-like statements like "break".
If you enjoy thinking about that, book VII of Euclid would be right up your alley: https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/book...
The algorithm you describe is VII Proposition 1.
The algorithm you describe is VII Proposition 1.
Off-topic, a question about the notation used for multiplication in this article.
I'm used to see multiplication written as 3⋅12 or sometimes 3×12, but recently I encountered this notation using parentheses, 3(12), and now I see that in this article too. Is that commonly used? It looks weird to me, and not very readable, perhaps just because I'm not used to it. To me 2⋅2⋅2⋅3⋅7 is much more readable than 2(2)(2)(3)(7) (which at first sight looks like function calls to me). Is the parentheses-notation used just to get rid of the explicit multiplication sign?
I guess there are situations where you can't easily use a proper multiplication sign, in which case I can see the parentheses notation as an effective alternative. But I've seen it used in handwritten equations too, so that can't be the only explanation.
Just wondering.
I'm used to see multiplication written as 3⋅12 or sometimes 3×12, but recently I encountered this notation using parentheses, 3(12), and now I see that in this article too. Is that commonly used? It looks weird to me, and not very readable, perhaps just because I'm not used to it. To me 2⋅2⋅2⋅3⋅7 is much more readable than 2(2)(2)(3)(7) (which at first sight looks like function calls to me). Is the parentheses-notation used just to get rid of the explicit multiplication sign?
I guess there are situations where you can't easily use a proper multiplication sign, in which case I can see the parentheses notation as an effective alternative. But I've seen it used in handwritten equations too, so that can't be the only explanation.
Just wondering.
which at first sight looks like function calls to me
This is at least consistent. Let's try to think of numbers as functions. Then dots or juxtaposition must mean function composition, right? Then, f(x)=f⋅x is consistent with arithmetic as we know it and this dual interpretation of dots. I suspect that it's also the only such consistent mapping from numbers to functions, but couldn't prove this right away.
This is at least consistent. Let's try to think of numbers as functions. Then dots or juxtaposition must mean function composition, right? Then, f(x)=f⋅x is consistent with arithmetic as we know it and this dual interpretation of dots. I suspect that it's also the only such consistent mapping from numbers to functions, but couldn't prove this right away.
[deleted]
I usually only recall seeing it where it's the expansion or replacement of a variable with the actual value, when solving equations or similar. It's not great. I've seen it used in a text talking about programming, with letters: so a(x) was actually multiplication but looked exactly like a function. Ugh!
Yes, it is extremely common. What country are you from?
It is used particularly in things like 3(x + 5) or (a + b)(a - b).
It is used particularly in things like 3(x + 5) or (a + b)(a - b).
Yes, of course, I do know that. It's not what I meant.
Suppose we expand that first example. I would write: 3(x + 5) = 3x + 3⋅5 The notation I'm talking about writes: 3(x + 5) = 3x + 3(5)
It's that 3(5) instead of 3⋅5 I'm talking about.
Suppose we expand that first example. I would write: 3(x + 5) = 3x + 3⋅5 The notation I'm talking about writes: 3(x + 5) = 3x + 3(5)
It's that 3(5) instead of 3⋅5 I'm talking about.
I prefer to use a dot like you, but find calculations like "let x=5, then 3(1+x) = 3(1+5) = 3(6) = 18" acceptable, because each equation is just a lock substitution
In your examples, it's not the brackets signifying the multiplication. It's the adjacency that signifies the multiplication (as in e.g. 3x) and in they happen to need brackets to highlight the precendence which would be lost in e.g. 3x + 5.
The notation of the article logically follows because e.g. (4) = 4 but using that as a "cheat" to enable multiplication of numeric literals using adjacency is very rare I think.
The notation of the article logically follows because e.g. (4) = 4 but using that as a "cheat" to enable multiplication of numeric literals using adjacency is very rare I think.
No, it's not rare. It's still quite common when you have people manipulating literal numbers. The literal numbers are what's rare.
In (high energy) physics the digits in the parenthensis states the error bar.
It’s not uncommon to write a x b as ‘ab’. So if you wanted to put two literals together using this syntax you could wrap one in brackets.
Somewhere in all the EWDs, EWD notes that the symmetric nature of GCD by subtraction means that it could be carried out by two concurrent processes, making it a very useful toy.
¿https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/E...?
“It is a very one-sided view to regard programs as “things to execute automatically”: they are also things to design, to enjoy, to embellish, to talk about and to use as a means of communication, either with yourself or with someone else“
“It is a very one-sided view to regard programs as “things to execute automatically”: they are also things to design, to enjoy, to embellish, to talk about and to use as a means of communication, either with yourself or with someone else“
> If someone has a better explanation of why subtracting relatively prime numbers repeatedly will always result in one, please leave a comment or reach out and help me understand better.
You're looking for a proof of Bezout's identity, or something in the spirit of that theorem :) to be honest, I haven't seen a proof of it that I "really really like", although you might find one
You're looking for a proof of Bezout's identity, or something in the spirit of that theorem :) to be honest, I haven't seen a proof of it that I "really really like", although you might find one
[deleted]
thank you, at first glance I couldn't see its reduction to this case but I will sit with it more. But if you can show me how it applies here I will appreciate that as well.
Here is Euclid's algorithm running on a relay computer:
https://www.youtube.com/watch?v=k1hJoalcK68
https://www.youtube.com/watch?v=k1hJoalcK68
For those in the commonwealth, HCF seems to be the preferred term than GCD, I wonder what is the basis for this difference..
int gcd(int a, int b) { while (b != 0) { int c = a % b; a = b; b = c; } return a; }
I think it is a rather efficient algorithm because it only has one test, one operation and two assignments. A good optimizing compiler could turn the loop in four instructions.