//Kishore Kulkarni / Haimonti Dutta 
//Problem Set:3, Question 1
//FILE:gcd.c

//Program to find the gcd of 2 numbers.
//The program calculates the processor time required for gcd algorithm.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>


void main()
{
	long int gcd(long int n,long int q);
	long int m,n,d;
	
	clock_t start_time, finish_time;
	double processor_time;
	
	printf("Enter the first number\n");
	scanf("%ld", &m);

	printf("Enter the second number\n");
	scanf("%ld", &n);

	//Note the start time of the algorithm.

	start_time=clock();

	//Call the function which executes the algorithm.

	d=gcd(m,n);

	//Note the finish time of the algorithm.

	finish_time=clock();

	//Calculate the processor time in nanoseconds.

	processor_time = (pow(10,9)*(double)(finish_time - start_time)) / CLK_TCK;

	//Print the processor time.
	//Print the gcd.
	
	printf("gcd=%d\n",d);

	printf("The Processor Time is: %lf nanoseconds\n",processor_time);

	// NOTE : As the running time is very very less (much less than a nanosecond) the answer displayed is generally zero. 
	
}



// Function to find the gcd.

long int gcd(long int m,long int n)
{
	// The worst case running time of each of the step is mentioned in the comments.
	// Worst Case Running Time = O(1) * O(log n) = O(log n).
	
	long int temp;

	// O(1)
	
	if(m<n) 
	{
		temp=m;
		m=n;
		n=temp;
	}

	// O(1)


	// O(Number of Recursions) = O(log(Smaller Number)) = O(log n)
	
	if(n==0) 
		return m;
	else
		return gcd(n, m%n);

	// O(Number of Recursions) = O(log(Smaller Number)) = O(log n)
}