Write a program that implements Euclid's extended algo- rithm. Then perform the following experiment: run it on a random selection of inputs of a given size, for sizes bounded by some parameter N; compute the average number of steps of the algorithm for each input size n < N, and use gnuplot to plot the result. What does f(n)-which is the "average number of steps" of Euclid's extended algorithm on input size n-look like? Note that size is not the same as value; inputs of size n are inputs with a binary representation of n bits.