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.
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.
It is used particularly in things like 3(x + 5) or (a + b)(a - b).
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.
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.
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.
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.
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.)
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!
Nonzero a, that is.
In general Euclid's algorithm is a special case of Buchberger's algorithm, q.v., if interested.
Thanks about the Buchberger intro I didn't know about that.
Also, Buchberger is a special case of Knuth-Bendix completion :D
"quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide .
https://www.amazon.com/Ideals-Varieties-Algorithms-Computati...
covers much of this topic
WHILE a < b DO
b := b - a
ELSIF a > b DO
a := a - b
END
while true do
if condition 1 do
statements 1
done
else if condition 2 do
statements 2
done
else do
break
done
doneI'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.
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
“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“
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
The algorithm you describe is VII Proposition 1.