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) {
    let r: number = m % n // E1
    if (r == 0) return n // E2

    // E3
    m = n
    n = r
  }
}

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

Algorithm Structure

Algorithm F (Factorial). Given a positive integer , find the factorial of , that is, the product of all numbers .

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

        flowchart LR
        F1[F1. Initialize $$f$$.]
        F2[Is it 1?]
        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.

The assigns the result of an expression to a variable. In this case is assigned to the variable .

Check if is equal to .

Swap the values of and .

Assign variables and to the result of the expression, in this case .

If condition, do something

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

Indicates the end of the algorithm.

The th element of array .

The th element of the th array in the multi-dimensional array .

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 and , Knuth's goal is to demonstrate that the divisors of and are the same as the divisors for and . 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 and is to demonstrate that is a subset of () and . Demonstrating that one set is a subset of another involves taking a value in the smaller set () and showing . For convenience, we'll define and as follows:

The set of divisors of and .

The set of divisors of and .

When Knuth points out that demonstrates that if a number divides both and it must therefore divide , he is implicitly stating that . Similarly, implies that .

So because , the set of divisors for and is the same as the set of divisors for and . Therefore, the largest divisor remains the same after step E3 is applied.

Worked Example of

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

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 . When is applied to this state, a new state (also in ) is produced:

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

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

Notice how information is stripped from , this is because it's the result and therefore a member of . Because the algorithm is complete, .

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

This sequence is collectively referred to as a computational sequence, with this particular example defined by . This one terminates in steps because step is the first step where a member of 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 and 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 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

Let's look at how to implement addition with the framework Knuth set forth to understand how it works. If we want to represent , the input could be or . Here is the process we want to create:

Transformations only occur when matches a part of the string, so in each step we want a to transform into an . To accomplish this, we can define and . This should be applied repeatedly until there are no more s, so will repeat the rule until no longer matches. Once all of those have been replaced, we need to move on to a new rule so , but we have the desired result so .

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

This can be done with , , and . The value is where we'll accumulate the result, so now that we're done with the leading it can be discarded with , , . We'll defer definition of for the moment, as once there are no more values it's time to move to a new stage in the algorithm. Here is what we have at this point:

For to apply successfuly to the next , though, the values must all be adjacent to the leftmost . So , and . With that it's possible to evaluate again, so .

Applying this process repeatedly will eventually reach , which means that does not apply and so . This step eliminates all values of with , , and . We'll consider strings exclusively containing as the output, so .

Here is a tool to explore this more fully:

4

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

Exercise and Answer Clarifications

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

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