eLa1: GCD algorithm, due date: 11/05/2014 8:00 am
1, Write a program that calculates the GCD using the 3 different algorithms discussed in class: subtraction- and modulo-based Euclidean algorithms, and prime factorization algorithm.
2.Compute the GCD for a series of pairs (a,b) of pseudo-random numbers and compare the number of steps required by the 3 algorithms versus (a+b)/2. Consider a large interval of values for the pseudo-random number, ex: 10000 to 1000000.
3.Do the same as in task 2 but compare CPU-time required by the 3 algorithms versus (a+b)/2. For this, do not obtain the CPU-Time only once but compute the average and standard deviation over a large number of trials, take a large number of trials, ex: 100000.
4.Post 2 graphs or plots showing your results in moodle - eLa1. Your graphs should contain three curves, one for each algorithm.