#include <iostream>
#include <cstdlib>

using namespace std;

int gcd_iterations(int a, int b, int iters){
	if (b > a){
		return gcd_iterations(b, a, iters+1);
	}
	int r = a % b;
	if (r == 0){
		return iters;
	} else {
		return gcd_iterations(b, r, iters + 1);
	}
}

int main() {
    int loops = 30000;
    int i, sum, a, b;
    
    sum = 0;
    for (i = 0; i < loops; i++)
    {
    	a = rand();
    	b = rand();
    	sum += gcd_iterations(a, b, 1);
    }
    float avg;
    avg = (float) sum / (float) loops;
	cout << avg << endl;
	cout << "sample inputs: " << a << " and " << b << endl;
	cout << "Bits of an int " << sizeof(int) * 8 << endl;
    a = 1836311903;
    b = 1134903170;
    cout << "Iterations at F44, F43 " << gcd_iterations(a, b, 1) << endl;
	return 0;
}