Euclid's Algorithm

Once you've stepped through Euclid's algorithm by hand, you may want to see a few more examples without the tedious calculations. Feel free to enter whatever values you want into the first row to see it in action:

Implementation

export function euclids_algorithm(m: number, n: number) {
  while (true) {
    const r: number = m % n // E1
    if (r == 0) return n // E2

    // E3
    m = n
    n = r
  }
}

export function euclids_algorithm(m: number, n: number) {
  const r = m % n
  if (r == 0) return n
  return euclids_algorithm(n, r)
}

Algorithm Structure

Algorithm F (Factorial). Given a positive integer $n$, find the factorial of $n$, that is, the product of all numbers $1,2,\dots ,n$.

• F1. [Initialize f.] Set $f\leftarrow n$.
• F2. [Is it 1?] If $n=1$, the algorithm terminates; $f$ is the answer.
• F3. [Reduce.] Set $n\leftarrow n-1$, $f\leftarrow f\cdot n$, and go back to step F2.

        flowchart LR
        accTitle: Flowchart of Algorithm F, Factorial
        accDescr: Start leads to F1, Initialize f. F1 leads to F2, is it 1. If no, F2 leads to F3, Reduce, which loops back to F2. If yes, F2 leads to Result.
        F1[F1. Initialize $$f$$.]
        F2[F2. Is it 1?]
        F3[F3. Reduce.]
        Start --> F1 --> F2 -- No --> F3 --> F2
        F2 -- Yes --> Result
        

Notation Reference

Algorithm F

Reference to an algorithm within the current section.

Algorithm 1.1E

Reference to an algorithm in a different section. For algorithms written on this site (like Algorithm F above) they will be referenced as W1.1F.

$x\leftarrow 2^{10}$

The $\leftarrow$ assigns the result of an expression to a variable. In this case $1024$ is assigned to the variable $x$.

$x=y$

Check if $x$ is equal to $y$.

$x\leftrightarrow y$

Swap the values of $x$ and $y$.

$x\leftarrow y\leftarrow 3^4$

Assign variables $x$ and $y$ to the result of the expression, in this case $81$.

If condition, do something

Perform "something" only if "condition" is true.

$$

Indicates the end of the algorithm.

$a[i]$

The $i$th element of array $a$.

$m[i,j]$

The $j$th element of the $i$th array in the multi-dimensional array $m$.

Algorithm Feature Reference

Finiteness

An algorithm eventually terminates.

Definiteness

Each step of an algorithm contains no ambiguity.

Input

An algorithm takes zero or more inputs and defines its constraints.

Output

An algorithm has at least one resulting value which relates to the input.

Effectiveness

Operations of an algorithm are simple enough that they can be worked out by hand.

Algorithm E Correctness Proof Explanation

Since E3 changes the values of $m$ and $n$, Knuth's goal is to demonstrate that the divisors of $m$ and $n$ are the same as the divisors for $n$ and $r$. If this is accomplished, then of course the greatest value in that set will remain the same.

The typical strategy when proving equivalence of sets, say $A$ and $B$ is to demonstrate that $A$ is a subset of $B$ ($A\subseteq B$) and $B\subseteq A$. Demonstrating that one set is a subset of another involves taking a value in the smaller set ($x\in A$) and showing $x\in B$. For convenience, we'll define $A$ and $B$ as follows:

$A$

The set of divisors of $m$ and $n$.

$B$

The set of divisors of $n$ and $r$.

When Knuth points out that $m-qn=r$ demonstrates that if a number divides both $m$ and $n$ it must therefore divide $r$, he is implicitly stating that $A\subseteq B$. Similarly, $qn+r=m$ implies that $B\subseteq A$.

So because $A=B$, the set of divisors for $m$ and $n$ is the same as the set of divisors for $n$ and $r$. Therefore, the largest divisor remains the same after step E3 is applied. $$

Worked Example of $T_3$

Here are the operations involved in calculating the individual values for $m$:

$m=1$

1. $r\leftarrow 1$
2. $r\leftarrow 0$

$m=2$

1. $r\leftarrow 2$
2. $r\leftarrow 1$
3. $r\leftarrow 0$

$m=3$

1. $r\leftarrow 0$

Explanation of Set Theory Grounding

To understand the set theory grounding, consider step E3. The information delivered to the step, along with the step number itself, form a packet of information describing the state of the machine executing the algorithm at that point:

This state is one element of $Q$. When $f$ is applied to this state, a new state (also in $Q$) is produced:

Every combination of values for each of these steps forms additional elements of the set $Q$. Also included in $Q$ are the members of $I$, which are bare pairs of $m$ and $n$:

Because E2 can branch depending on the value of $r$, the output from that step has two separate forms:

Notice how information is stripped from $f(s_2)$, this is because it's the result and therefore a member of $\mathrm{\Omega }$. Because the algorithm is complete, $f(f(s_2))=f(s_2)$.

Let us look again at the example worked in the book of $(119,544)$, applying $f$ repeatedly eventually leads to the output $(17)$. Alongside each step, I've included the applicable portion of the equation Knuth provides.

This sequence $x_0,x_1,\dots ,x_{15}$ is collectively referred to as a computational sequence, with this particular example defined by $(119,544)$. This one terminates in $15$ steps because step $15$ is the first step where a member of $\mathrm{\Omega }$ is encountered.

For this mathematical model to be an algorithm, it must meet the five criteria outlined earlier in the section. As mathematical equations, they are by their nature definite, and the sets $I$ and $\mathrm{\Omega }$ ensure that there is iput and output. Finiteness is an additional constraint: all possible inputs must define computational sequences which terminate in a finite number of steps.

Effectiveness must also be achieved via additional constraints, but this can be accomplished by a number of different approaches. The discussion around $A^{\ast }$ is one example of this, constraining the expression of algorithms to mutating sequences of letters, which of course can be written down and therefore worked by hand.

Using $A^{\ast }$

Let's look at how to implement addition with the framework Knuth set forth to understand how it works. If we want to represent $3+5$, the input could be $aaabbbbb$ or $a^3{b}^5$. Here is the process we want to create:

Transformations only occur when ${\theta }_j$ matches a part of the string, so in each step we want a $b$ to transform into an $a$. To accomplish this, we can define ${\theta }_0=b$ and ${\varphi }_0=a$. This should be applied repeatedly until there are no more $b$s, so $b_0=0$ will repeat the rule until ${\theta }_0$ no longer matches. Once all of those have been replaced, we need to move on to a new rule so $a_0=1$, but we have the desired result so $N=1$.

Now consider multiplication, which is a little more complicated to model. To begin, we want to take a $b$ and add a new value $c$ into the mix for each $a$:

This can be done with ${\theta }_0=ab$, ${\varphi }_0=bac$, $b_0=0$ and $a_0=1$. The $c$ value is where we'll accumulate the result, so now that we're done with the leading $b$ it can be discarded with ${\theta }_1=ba$, ${\varphi }_1=a$, $b_1=2$. We'll defer definition of $a_1$ for the moment, as once there are no more $ba$ values it's time to move to a new stage in the algorithm. Here is what we have at this point:

For $j=0$ to apply successfuly to the next $b$, though, the $a$ values must all be adjacent to the leftmost $b$. So ${\theta }_2=ac$, ${\varphi }_2=ca$ and $b_2=2$. With that it's possible to evaluate $j=0$ again, so $a_2=0$.

Applying this process repeatedly will eventually reach $c^{15}{a}^3$, which means that ${\theta }_1$ does not apply and so $a_1=3$. This step eliminates all values of $a$ with ${\theta }_3=a$, ${\varphi }_3=\text{empty}$, $b_3=3$ and $a_3=4$. We'll consider strings exclusively containing $c$ as the output, so $N=4$.

Here is a tool to explore this more fully:

Add rule Export CSV Import CSV Copy share link

$N=$ 4

Enter a string below to watch the algorithm above apply to it, one stage at a time:

Maximum steps Collapse to start and end

Exercise and Answer Clarifications

3. It's unclear from the problem statement that assignment isn't entirely disallowed. So even though $m\leftarrow n$ is disallowed, expressions like "Divide $m$ by $n$ and let $m$ be the remainder" still appears in the solution.

6. This is asking you to replicate the calculation for each possible value of $m$, not apply the equation provided for the nature of $T_n$.