due Aug 8, in class.

1.  We showed that the number of iterations required for Euclid's
    algorithm was proportional to the log of the sum of the numbers,
    assuming that the numbers fit in one word, so that arithmetic
    operations can be done in one step.

    Show that the larger of the two numbers must decrease by a factor
    of at least 2 in every 2 iterations.  Give an example instance in
    which the decrease is very little if you consider one iteration.
    What does this analysis reveal?

2.  We argued that the number of iterations must be at most
    the log of the sum to base 1.5.  Can you give a lower bound,
    i.e. show that the iterations must be at least log of the sum to
    some base?  Experiment with numbers and see when the number of
    iterations is large.

3.  Give algorithms for x % y where x and y are b bit numbers, and b
    is also a part of the input.  For simplicity you may assume that
    on your computer you use a single word for storing each bit.  How
    much time is needed as a function of b?  You may need routines for
    subtracting/comparing b bit numbers which you should describe.

4.  Using the algorithms above estimte the time taken to find the GCD
    of b bit numbers, where b is given as a part of the input.
    Express the time taken as a function of the number of bits of the
    numbers whose GCD is to be computed, and not their magnitudes.

5.  An equation such as 79x + 37y = 634 with the restriction that x
    and y must be integral is said to be a (linear) Diophantine
    equation.  Devise an algorithm to find a solution.

    Hint: Use recursion.  Can you construct a smaller problem instance
    given a solution of which you can get a solution for the original
    equation?

    Hint 2: Dont give up or look on the internet without trying a few
    (simple to start with) things yourself.  It is worth the
    satisfaction!