(Euclid's Algorithm) What does b←b-a and a←a-b mean?

Question

In the diagram below, what do steps 4 and 6? Is it the same as ⇒ where if the right is true, the left is true as well?

Diagram: https://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Euclid_flowchart.svg/399px-Euclid_flowchart.svg.png

Answer 1

What it amounts to is finding the difference between $A,B$ and then repeating the pattern with the "smaller of $A,B$" and the "difference" until, effectively, $A-B=0$ e.g. $GCD(20,15)$. $$ 20-15=5\\ 15-5=10\\ 10-5=5\\ 5-5=0$$ So $GCD(20,15)=5$

A faster implementation requiring only $2$ iterations for this example uses "mod" as shown in the BASIC below.

  100 input i1
  110 input i2
  120 x1 = i1
  130 x2 = i2
  140 r1 = x1 mod x2
  150 c1 = c1+1
  160 if r1 > 0
  170    x1 = x2
  180    x2 = r1
  190 goto 140
  200 endif
  210 print c1 "iterations",;
  220 print "GCD(" i1 i2 ") = " x2
  

Answer 2

If you're familiar with a coding language like Python, C, or Java, $a \gets b$ is equivalent to the statement $a = b$ in one of those languages.

If you're not familiar with those languages, allow me to give a brief explanation.

When one discusses algorithms, one uses variable names like $a$ and $b$ to represent the "contents of a box". Instead of $a$ representing a fixed value, $a$ is really the name of a box which holds a value.

When we want to use the value contained in box $a$, we refer to this value as $a$. For example, if one wrote the expression $2 \cdot a$, evaluating this expression would require you to look inside box $a$, get the value, and multiply that value by 2.

However, on some occasions, one might want to change the value inside box $a$. To do this, we use an "assignment statement" of the form $a \gets E$, where $E$ is some expression.

For example, in the pseudocode

a <- 1;
b <- a + 1;
a <- b;
b <- a + 1;

the final value in box $a$ is 2, and the final value in box $b$ is 3.