Computer Science 2611
Fall 2004
Laboratory Assignment 1

Handed out: 8/30/04

You should find this a challenging assignment. Follow the instructions. Ask questions when you have trouble and do not see what to do.

Accounts

You should have an account on the Unix machines in room 208. If you have an account from a prior term, your account has not changed. If you do not already have an account, you will be given the password. Your account also works on the Windows machines in room 209, with the same password. You can use the same files from both Unix and Windows.

If you have a new account, then when you log in you will see a small window in the corner of the screen asking you to change your password. Move the mouse into that window. Type your old password, then your new password twice, with a return after each one. You should get another login screen. You only need to do this once.

If you have difficulty with your account, ask for help.

Links

You might want to look at the following links.

• Compiling and running programs
• Notes on using Solaris

Terminology, facts and an algorithm

All of the numbers for this assignment are nonnegative integers.

The greatest common divisor of two numbers n and m, written gcd(m,n), is the largest number k such that k is a divisor of both m and n. For example,

• gcd(15,35) = 5
• gcd(52,20) = 4
• gcd(5,7) = 1

A naive algorithm

One way to find the greatest common divisor of m and n is to try each possible number, starting at the smaller of m and n and counting down until a divisor of both is found. Here is a function definition in C++ that uses this approach. It uses type long for integers. We have not discussed functions yet, but look at the part inside the function that does the work.

  long gcd(long m, long n)
  {
    long k;

    //----------------------------------
    // Make k be the smaller of m and n.
    //----------------------------------

    if(m < n) k = m;
    else k = n;

    //-------------------------------------------------
    // Decrease k until k is a divisor of both m and n.
    //-------------------------------------------------

    while(n % k != 0 || m % k != 0) 
    {
      k = k - 1;
    }

    return k;
  }

Another (still naive) algorithm

Another approach is to find the prime factorization of m and n, and to multiply together the common factors. That also turns out to be extremely slow for large numbers, because finding prime factors is difficult.

Computing remainders

When you learned division in grade school, you learned to compute a quotient and a remainder. For example, when you divide 20 by 3, you get a quotient of 6 and a remainder of 2.

Mathemeticians write x mod y to mean the remainder when you divide x by y. For example 20 mod 3 is 2, since when you divide 20 by 3, the remainder is 2.

C++ has a somewhat peculiar notation for the same thing. In C++, you write x % y for the remainder when you divide x by y. In a C++ program, I will write %, but when just discussing ideas, I will write the more common mod.

An efficient algorithm

The Greek mathematician Euclid discovered a simple and efficient way to find the greatest common divisor of two numbers quickly. It is based on the following facts.

(1)   gcd(0,n) = n
(2)   gcd(m,n) = gcd(n mod m, m) (when m > 0)

gcd(i,j) = gcd(j mod i, i) (when i > 0)

                i               j
              _____           _____
               10               36
                6               10
                4                6
                2                4
                0                2

Question: We tried Euclid's algorithm for m = 10 and n = 36. Does Euclid's algorithm work for the case of m = 36 and n = 10? Try it. The value of 10 mod 36 is 10. Try it by hand to see if it works.

The assignment, part 1

You want to write a program that reads two numbers m and n and prints their greatest common divisor. Here is a C++ program that does the job, using the naive algorithm for computing gcd. Copy this program from the browser to a text editor, and save it as prog1a.cpp. (Just mark the section with the mouse, use edit/copy, then go to the text editor and use edit/paste.)

  // Your name here
  // Computer science 2611
  // Programming assignment 1A, submission 1
  // August 30, 2004

  // This program reads two numbers from the user and
  // prints their greatest common divisor.

  #include<iostream>
  using namespace std;

  //===================================================
  //                  gcd
  //===================================================
  // gcd(m,n) returns the greatest common divisor of
  // m and n.
  //===================================================

  long gcd(long m, long n)
  {
    long k;

    //----------------------------------
    // Make k be the smaller of m and n.
    //----------------------------------

    if(m < n) k = m;
    else k = n;

    //-------------------------------------------------
    // Decrease k until k is a divisor of both m and n.
    //-------------------------------------------------

    while(n % k != 0 || m % k != 0) k--;

    return k;
  }

  //================================================
  //                    main
  //================================================
 
  int main()
  {
    long m,n,g;

    cout << "Compute the gcd of what two numbers?" << endl;
    cin >> m >> n;
    g = gcd(m,n);
    cout << "The gcd of " << m << " and " << n << " is " << g << endl;
    return 0;
  }

   g++ -Wall prog1a.cpp

   a.out

The assignment, part 2

Save your program as prog1b.cpp. Edit the comment at the top, since this is now assignment 1 part b. Now modify prog1b.cpp so that it uses Euclid's algorithm to compute greatest common divisors. That involves changing how the gcd function works. The form should be

  long gcd(long m, long n)
  {
    long i,j;

    ...

    return j;
  }

Be careful how you update i and j. Write the body of the loop, then do it by hand, using the example of 10 and 36. Do it by hand exactly the way it is written, not the way you wish it would work. If it does not work, how can you fix it? You might want another variable. Feel free to create another variable.

Turning on the lights

Good programmers do not just presume that their programs work. They turn on the lights to see what is happening. Make your function print the values of i and j each time around the loop. Just inside the loop, put

  cout << i << "  " << j << endl;

The assigmnent, part 3

Save your program as prog1c.cpp. Remove the trace print from it. Compile it and run it. Does it seem to work? Try it on some numbers that are exactly 9 digits long. Is it more efficient than the naive algorithm?

Turning in the assignment

Print all three versions, prog1a.cpp, prog1b.cpp and prog1c.cpp. You can print using the print button in the text editor. You can also print prog1a.cpp by giving command

   lpr prog1a.cpp