#include <iostream>
#include <string>
#include <utility> // Required for std::pair
#include <tuple> // Required for std::tuple
#include <map> // Required for std::map
using namespace std;


map<string,int> divide_m(int dividend, int divisor){
	int quotient = 0;
	int remainder = dividend;
	map <string, int> result;

	while(dividend > divisor and remainder >= divisor){
		remainder -= divisor;
		quotient++;	
	}
	
	result["quotient"] = quotient;
	result["remainder"] = remainder;

	return result;
}


pair<int,int> divide_p(int dividend, int divisor){
	int quotient = 0;
	int remainder = dividend;

	while(dividend > divisor and remainder >= divisor){
		remainder -= divisor;
		quotient++;	
	}

	pair <int, int> result(quotient,remainder);	
	return result;
}


tuple<int,int> divide_t(int dividend, int divisor){
	int quotient = 0;
	int remainder = dividend;

	while(dividend > divisor and remainder >= divisor){
		remainder -= divisor;
		quotient++;	
	}

	tuple <int, int> result(quotient,remainder);	
	return result;
}


double goldschmidt(int dividend, int divisor){
	// quotient = n/d
	double n,d,f;
	n = double(dividend);
	d = double(divisor);
	f=0.1;
	bool done = false;
	char choice = 'n';
	while(not done and d != 1){
		cout << "Dividend (n): " << n << endl;
		cout << "Divisor: (d): " << d << endl;
		cout << "Factor (f): " << f << endl;
		n *= f;
		d *= f;
		f = 2 - d;
		cout << "Next approximation? (y/n): ";
		cin >> choice;
		if (choice != 'y'){
			done = true;
		}
	}
	return n;
}



int main(){
	int dividend, divisor;
	map <string, int> result_m;
	pair <int, int> result_p;
	tuple <int, int> result_t;

	cout << "*** \"Slow\" Division ***\n";
	cout << "Enter the dividend (the number to be divided): ";
	cin >> dividend;
	cout << "Enter the divisor (the number you are dividing by): ";
	cin >> divisor;

	// using map:
	result_m = divide_m(dividend, divisor);
	cout << "Quotient: " << result_m["quotient"] << endl;
	cout << "Remainder: " << result_m["remainder"] << endl;

	// using pair:
	result_p = divide_p(dividend, divisor);
	cout << "Quotient: " << result_p.first << endl;
	cout << "Remainder: " << result_p.second << endl;

	// using tuple:
	result_t = divide_t(dividend, divisor);
	cout << "Quotient: " << get<0>(result_t) << endl;
	cout << "Remainder: " << get<1>(result_t) << endl;

	cout << "*** \"Fast\" Division (Goldschmidt: decimal)***\n";
	cout << "Quotient: " << goldschmidt(dividend,divisor) << endl;

	return 0;
}