GCD Models Help

 

There are three different models in this directory that are used to show the Greatest Common Divisor algorithm (GCD). This file will help you use the models.

 

To get started you will need to load the TkEden program.

 

From the File menu choose the Execute option. This loads a dialog box which – when you have set the correct directory – looks like the one below:

 

 

Choose the file Run1.e by double clicking on it.

 

You will now have to wait for a while as this file is processed. When it has loaded you can resize the window by dragging the window to make it bigger.  You should see a screen like the one below:

 

 

There are two numbers in the cells A2 and B2. To change them we need to type commands into the TkEden input window.

 

To change the value ‘m’ in cell A2 we can enter a command like m=9; into the window and then click on the Accept button. You should see the value in cell A2 change.

 

To change the value ‘n’ in cell B2 we can enter a command like n=39; into the window and then click on the Accept button. You should see the value in cell B2 change.

 

To run the standard GCD algorithm we enter the command GCD(); into the window and then click on the Accept button.

 

You should see the screen like the picture below:

 

 

To try another pair of numbers, click on the Reset button in cell E1. This restores the values to those that we had on the initial screen.

 

Exercise:

 

There is an alternative GCD algorithm (the ‘Binary GCD Algorithm’) that can be studied in a rather similar manner. This GCD algorithm is well-suited to the specific operations that are supported by a computer. For instance, many steps of the algorithm include multiplication and division by 2, which are easily performed in computer hardware as shifts of binary strings of 0’s and 1’s.

 

Both the binary GCD algorithm and the standard GCD algorithm rely on a similar principle: they manipulate the values of m and n so that GCD(m,n) remains unchanged, but m and n become progressively smaller, until eventually the value of the GCD can be specified directly. The simplification process relies on the following facts:

·        if m and n are both even, then GCD(m,n) is 2 * GCD(m/2, n/2)

·        if m is even and n is odd, then GCD(m,n) is GCD(m/2, n)

·        if m and n are both odd, and m>n, then GCD(m,n) is GCD(m-n, n)

·        if m and n are both odd, and n>m, then GCD(m,n) is GCD(m, n-m)

·        if m and n are both odd, and n=m, then GCD(m,n) is m.

 

The listing for a TkEden version of the binary GCD algorithm is given below:

 

func bin_gcd {

      para m, n;

      /* two non-negative integers input, not both zero */

      auto answer, pot;

      pot=0;

      if (m*n==0) answer = m+n; /* if m is zero, gcd = n and v.v. */

      else {     

            /* deal with case of both m and n even */

            while (is_even(m) && is_even(n)) {

                  pot++;

                  m = m/2;

                  n = n/2;

            }

            /* hereafter at most one of m and n is even */

            while (m!=n) {

                   /* discard factors of 2 from m xor from n */

                  while (is_even(m)) m = m/2;

                  while (is_even(n)) n = n/2;

                  /* make progress if m and n both odd and not equal */

                  if (m>n) m = m-n;

                  else

                  if (n>m) n = n-m;

            }

            answer = m; /* because m = n */

            /* restore the common factors of 2 taken out initially */

            while (pot!=0) {

                  answer = 2*answer;

                  pot--;

            }

      }

      return answer;

}

 

To run the binary GCD algorithm, you should first use the Reset button to restore m and n to the default values 1 and 0, then assign the required input values to m and n. You can then type BIN_GCD(); in the TkEden input window.  In the spreadsheet display, the columns record the successive values of m and n, together with the largest power of 2 that m and n have in common, and GCD(m,n) in a highlighted cell.  The various phases of the algorithm are indicated by grouping the values that appear in each column into blocks, as in the computation of GCD(248,126) in the display below:

 

The third GCD model uses the dependencies between spreadsheet cells to compute the greatest common divisor of m and n directly. To set up the model, quit the TkEden program, by selecting the ‘quit’ option from the File menu. Restart TkEden, and (in a similar manner to before) load the file Run2.e.

 

To compute the GCD of two numbers m and n, simply enter definitions for m and n in the input window.  For instance, enter

 

m = 18; n = 12;

 

to get the following display:

 

 

The idea behind this variant of the GCD is that the definitions needed to compute each line in the spreadsheet display are built-in to the model. You can see these definitions by entering showdeps(); into the input window, and restore the values to the spreadsheet by entering showvalues(); . The definitions will appear somewhat complicated, but their essential form is quite simple. To confirm this you can enter the following simpler definitions in the input window:

 

 

By experiment, you can check that these simpler definitions will work fine for any values of m and n such that the GCD computation needs at least two steps. (But there will be a problem if you take m = 4 and n = 2 for instance!) The actual definitions used in the original model are more complex because they allow for any number of steps up to a maximum of 24 in the GCD computation. (If you want to restore the original definitions, you will need to reload the entire GCD model, or retype the original definitions for the cells C2, D2, A3, B3, C3, D3, A4, B4 directly into the input window.)

 

Question: What are the smallest values of m and n that exceed the maximum 24 steps provided for in this GCD model?

 

Answer: Examine what happens when the values of m and n are F[k+1] and F[k] respectively, where F[k] are taken from the Fibonacci sequence. Use the script provided in the supporting mathematical notes to calculate and enter suitable values from the Fibonacci sequence to completely fill the spreadsheet array. Can you see why this is a way of constructing the smallest values to fill the array?

 

Exercise: Imitate the construction of the third GCD model to implement an algorithm that is based on the so-called subtractive form of  Euclid’s GCD algorithm:

 

func gcd {

      para m, n;

      /* two non-negative integers input, not both zero */

      while (m!=n) {

            if (m>n) m = m-n;

            else

            if (m<n) n = n-m;

      }

      return m;

}