// Classical algorithms namespace implementation file

#include <stdafx.h>

#include<math.h>
#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<time.h> 

#include "calgos.h"

int CCAlgos::euclid(int x, int y)
{
	while(x != y)
	{
		if(x>y)
			x-=y;
		else
			y-=x;
	}

	return x;
}

int CCAlgos::coprime(int x)
{
	int y;

	for(;;)
	{
		y = (rand() % (x - 2)) + 2;
		if(euclid(x,y) == 1)
			break;
	}

	return y;
}

int CCAlgos::approxdenom(double rational, int max)
{
	// max*max complexity - not very efficient!

	// also since rational x = a/b
	// we really only need one loop as a = bx,
	// i.e b is automatically defined for each a.
	// need to implement this when time permits

	if((rational - floor(rational)) == 0)
		return 1;	// its an integer

	double error = 1, min_error;

	int denominator, numerator;

	for(int i = 0; i < max; i++)
	{
		for(int j = 0; j < max; j++)
		{
			if(i <= j)	// if not its not a fraction
			{
				error = fabs((double)i/(double)j - rational);
				if(error < min_error)
				{	
					min_error = error;
					numerator = i;
					denominator = j;
				}
			}
		}
	}

	return denominator;
}