The Chinese University of Hong Kong

Department of Computer Science and Engineering

CEG2400 Microcomputer Systems

Tutorial 4


In the lab session on 4th March 1998, you are required to submit a listing of your solution and demonstrate it to the TA.
  1. There is a well known algorithm by Euclid to calculate the greatest common divisor (GCD) of two integers. The algorithm can be expressed as the following pseudocode 
    
function gcd(a, b)
{
   var r, x, y
   x = a
   y = b
   while (y != 0)
   {
      // Invariant:
      // gcd(a,b)=gcd(x,y) 
      r = x % y
      x = y
      y = r
   }
   return x
}
    Write a program to calculate the GCD of two unsigned 16 bit numbers using Euclid's algorithm. The program should take two base 10 numbers entered via the keyboard, and print the GCD out in base 10.