6 ms·

GCD and the magic of subtraction

67 points by plumsempy 6y ago

082349872349872 6y ago
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.
- Someone 6y ago
  ¿https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD398.html 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“
pansa2 6y ago
Something I spotted: Your diagram of “common and uncommon parts of 36(4×9) and 45(5×9)“ actually shows 108(4x27) and 135(5x27).
- plumsempy 6y ago
  oops! thanks for noticing. Will correct it soon.
fjfaase 6y ago
I usually use this algorithm (in C-like syntax) with modulo division: 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.
- edflsafoiewq 6y ago
  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.
- plumsempy 6y ago
  This is interesting. Thank you.
  - thaumasiotes 6y ago
    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: P1. z|a (in words, there is some integer m for which a = zm) P2. z|b Then these two propositions are also true: D1. z|b D2. z|r Once established, this will show that any integer evenly dividing both a and b also evenly divides both b and r, and thus GCD(a,b) = GCD(b,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) Since m, q, and n are all integers, so is (m-qn), and we have shown that z|r. 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) This completes the proof. ------- 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 these two propositions will be true: D1. z|b D2. z|r Step 3: P2 suffices to prove D1. 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 since m and n are both integers, (m - n) is an integer and z|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.)
jjtheblunt 6y ago
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.
- bollu 6y ago
  What's q.v? Also, Buchberger is a special case of Knuth-Bendix completion :D
  - JadeNB 6y ago
    > What's q.v? "quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide https://en.wiktionary.org/wiki/quod_vide .
    - m12k 6y ago
      So basically "see also" in Latin?
      - jjtheblunt 6y ago
        good point: "see" even by itself works, but i had lots of Latin so didn't think of it.
  - jjtheblunt 6y ago
    yep...fun stuff. https://www.amazon.com/Ideals-Varieties-Algorithms-Computational-Undergraduate/dp/3319167200/ https://www.amazon.com/Ideals-Varieties-Algorithms-Computati... covers much of this topic
- plumsempy 6y ago
  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.
roelschroeven 6y ago
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.
- benmmurphy 6y ago
  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.
- thaumasiotes 6y ago
  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).
  - quietbritishjim 6y ago
    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.
    - thaumasiotes 6y ago
      No, it's not rare. It's still quite common when you have people manipulating literal numbers. The literal numbers are what's rare.
wcarey 6y ago
If you enjoy thinking about that, book VII of Euclid would be right up your alley: https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/bookVII.html https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/book... The algorithm you describe is VII Proposition 1.
augustk 6y ago
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 WHILE a < b DO b := b - a ELSIF a > b DO a := a - b END The Oberon programming language by Niklaus Wirth supports the Dijkstra while loop. https://miasap.se/obnc/oberon-report.html#sec9.6 https://miasap.se/obnc/oberon-report.html#sec9.6
- whatshisface 6y ago
  Wouldn't that be `else: break` in every other language?
  - nils-m-holm 6y ago
    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 done
    - augustk 6y ago
      Oberon, however, is a purely structured language and has no goto-like statements like "break".
jhallenworld 6y ago
Here is Euclid's algorithm running on a relay computer: https://www.youtube.com/watch?v=k1hJoalcK68 https://www.youtube.com/watch?v=k1hJoalcK68
billfruit 6y ago
For those in the commonwealth, HCF seems to be the preferred term than GCD, I wonder what is the basis for this difference..
phaemon 6y ago
> 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": a - b = c ---------- 8 - 6 = 2 10 - 6 = 4 12 - 6 = 6 14 - 6 = 8 You can see what values of "a" are required to get a factor of "2" as the result, and at this point, I reckon most folk can see the flaw in this cunning plan. But let's rub the point in with 3: a - b = c ---------- 9 - 6 = 3 12 - 6 = 6 15 - 6 = 9 18 - 6 = 12 Again, you can see the result. In order for "b" to have a common factor with "c", "a" has to be some multiple more of that common factor. (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.
- plumsempy 6y ago
  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.
  - phaemon 6y ago
    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: 13 - 7 = 6 -> 7 - 6 = 1 a - b = c -> b - c = d But then then you do: 6 - 1 = 5 -> 5 - 1 = 4 a - b = c -> c - b = d Which switches the order. What if you don't?
zodiac 6y ago
> 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
- deleted 6y ago
  [deleted]
- plumsempy 6y ago
  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.

67 points by plumsempy 6y ago

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.

Someone 6y ago
¿https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD398.html 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“

pansa2 6y ago

Something I spotted: Your diagram of “common and uncommon parts of 36(4×9) and 45(5×9)“ actually shows 108(4x27) and 135(5x27).

plumsempy 6y ago
oops! thanks for noticing. Will correct it soon.

fjfaase 6y ago

I usually use this algorithm (in C-like syntax) with modulo division: 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.

edflsafoiewq 6y ago
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.
plumsempy 6y ago
This is interesting. Thank you.
- thaumasiotes 6y ago
  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: P1. z|a (in words, there is some integer m for which a = zm) P2. z|b Then these two propositions are also true: D1. z|b D2. z|r Once established, this will show that any integer evenly dividing both a and b also evenly divides both b and r, and thus GCD(a,b) = GCD(b,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) Since m, q, and n are all integers, so is (m-qn), and we have shown that z|r. 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) This completes the proof. ------- 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 these two propositions will be true: D1. z|b D2. z|r Step 3: P2 suffices to prove D1. 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 since m and n are both integers, (m - n) is an integer and z|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.)

jjtheblunt 6y ago

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.

bollu 6y ago
What's q.v? Also, Buchberger is a special case of Knuth-Bendix completion :D
- JadeNB 6y ago
  > What's q.v? "quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide https://en.wiktionary.org/wiki/quod_vide .
  - m12k 6y ago
    So basically "see also" in Latin?
    - jjtheblunt 6y ago
      good point: "see" even by itself works, but i had lots of Latin so didn't think of it.
- jjtheblunt 6y ago
  yep...fun stuff. https://www.amazon.com/Ideals-Varieties-Algorithms-Computational-Undergraduate/dp/3319167200/ https://www.amazon.com/Ideals-Varieties-Algorithms-Computati... covers much of this topic
plumsempy 6y ago
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.

roelschroeven 6y ago

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.

benmmurphy 6y ago
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.
thaumasiotes 6y ago
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).
- quietbritishjim 6y ago
  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.
  - thaumasiotes 6y ago
    No, it's not rare. It's still quite common when you have people manipulating literal numbers. The literal numbers are what's rare.

wcarey 6y ago

If you enjoy thinking about that, book VII of Euclid would be right up your alley: https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/bookVII.html https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/book... The algorithm you describe is VII Proposition 1.

augustk 6y ago

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 WHILE a < b DO b := b - a ELSIF a > b DO a := a - b END The Oberon programming language by Niklaus Wirth supports the Dijkstra while loop. https://miasap.se/obnc/oberon-report.html#sec9.6 https://miasap.se/obnc/oberon-report.html#sec9.6

whatshisface 6y ago
Wouldn't that be `else: break` in every other language?
- nils-m-holm 6y ago
  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 done
  - augustk 6y ago
    Oberon, however, is a purely structured language and has no goto-like statements like "break".

jhallenworld 6y ago

Here is Euclid's algorithm running on a relay computer: https://www.youtube.com/watch?v=k1hJoalcK68 https://www.youtube.com/watch?v=k1hJoalcK68

billfruit 6y ago

For those in the commonwealth, HCF seems to be the preferred term than GCD, I wonder what is the basis for this difference..

phaemon 6y ago

> 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": a - b = c ---------- 8 - 6 = 2 10 - 6 = 4 12 - 6 = 6 14 - 6 = 8 You can see what values of "a" are required to get a factor of "2" as the result, and at this point, I reckon most folk can see the flaw in this cunning plan. But let's rub the point in with 3: a - b = c ---------- 9 - 6 = 3 12 - 6 = 6 15 - 6 = 9 18 - 6 = 12 Again, you can see the result. In order for "b" to have a common factor with "c", "a" has to be some multiple more of that common factor. (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.

plumsempy 6y ago
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.
- phaemon 6y ago
  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: 13 - 7 = 6 -> 7 - 6 = 1 a - b = c -> b - c = d But then then you do: 6 - 1 = 5 -> 5 - 1 = 4 a - b = c -> c - b = d Which switches the order. What if you don't?

zodiac 6y ago

> 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

deleted 6y ago
[deleted]
plumsempy 6y ago
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.