#include<iostream>
#include<vector>
#include<cmath>
#include<chrono>
using namespace std;

// ChatGPT came up with this, and it works
#define TIME_CALL(FUNC_CALL)                            \
({                                                      \
    clock_t _start = clock();                           \
    __typeof__(FUNC_CALL) _result = (FUNC_CALL);        \
    clock_t _end = clock();                             \
    printf("Time taken: %.3f ms\n",                     \
           1000.0 * (_end - _start) / CLOCKS_PER_SEC);  \
    _result;                                            \
})

/* Notice that calculating fib(x - 1) actually also calculates fib(x - 2), and we need to
 * use the result instead of losing it.
 * There are basically three ways to solve this:
 * 	1.  Convert to an iterative function
 * 	2.  Multiple returns (use a struct, or pass a reference for the function change)
 * 	3.  Save a list of previously-computed values
 */
int fib(int x){
	if(x == 0)
		return 0;
	if(x == 1)
		return 1;
	return fib(x - 1) + fib(x - 2);
}

/* Just a helper for the next function.  Library round function rounds to the closest integer. */
double round_flexible(double n, double precision){
	return round(n / precision) * precision;
}

/* Returns true if the sin of pi is in the given list, to a precision of 1/10000 */
bool is_sine_of_pi_in_list(vector<double> nums){
	bool found = false;
	for(double n : nums)
		if(n == round_flexible(sin(3.141592653), 0.0001))
			found = true;
	return found;
}

/* Optimize both functions, so they still do the same thing but faster.
 * Standard for success:  Both functions <1 millisecond
 * I *think* this lab is is crazy-overclocked-gaming-computer safe, but if your computer is really
 * fast and you know it, don't give up at 0.99 milliseconds.
 */


int main(){

	cout << TIME_CALL(fib(35)) << endl;

/* If you don't have srandom and random, feel free to convert to srand and rand, or some other
 * random number libary */
	vector<double> values;
	srandom(1); // Consistent seeding
	values.reserve(5000000);
	for(int i = 0; i < 5000000; i++)
		values.push_back((double)(random() % 10000) / 10000.0);
	cout << TIME_CALL(is_sine_of_pi_in_list(values)) << endl;

	return 0;	
}