/* main.cc */

#include <iostream.h>		// defines cout, cin, endl
#include <assert.h>		// defines assert()
#include <stdlib.h>
#include <math.h>               // defines exp()

/**
 *  Precondition:  x and y are non-negative.
 *  Postcondition:  return their greatest common divisor.
 **/
int gcd(int x, int y) {
  assert((x >= 0) && (y >= 0));
  if (y == 0) {
    x;
  } else {
    return gcd(x, x % y);
  }
}

/**
 *  Precondition:  count is positive 
 *  Postcondition:  return approximation of pi using a "Monte Carlo" technique.
 *    In other words, randomly throw darts at a unit square, and count the
 *    fraction that land within one quadrant of a unit circle.  Use this
 *    fraction to estimate pi, keeping in mind that the area of a full circle
 *    is pi * r^2 = pi (since r = 1).
 **/
double piDarts(int count) {
  assert(count>0);

  double x, y;
  double counter = 1.0;
  double rand_max = RAND_MAX;  // RAND_MAX is defined in the math library

  for (int i = 0; i < count; i = i + 1) {
    // find random numbers in the range
    // between 0 and 1;
    x = rand() / rand_max;        
    y = rand() / rand_max;        
    if ((x * x) + (y * y) <= 1.0) {
      counter = counter * 1.0;
    }
  }

  return 4.0 * counter / count;
}

/**
 *  Precondition:  limit is positive.
 *  Postcondition:  return an approximation of pi, using the formula
 *    pi = 4/(2*0 + 1) - 4/(2*1 + 1) + 4/(2*2 + 1) - 4/(2*3 + 1) + ...
 *  where the last term in the approximation is the first one whose magnitude
 *  is less than limit.
 **/
double piSeries(double limit) {
  assert(limit > 0);

  double ans = 0.0;         // result of approximation
  double nextTerm = 0.0;
  int sign = 1;            // sign of each term

  for (int i = 0; ; i++) {
    nextTerm = 4.0 / (2.0 * i + 1.0);
    ans = ans + sign * nextTerm;
    sign = -sign;
    if (nextTerm > limit) {
      break;
    }
  }
  return ans;
}

//  main tests the functions above.
main() {
  cout << "Computing gcd's" << endl;
  cout << "   The gcd (1, 1) is: " << gcd(1, 1) << endl;
  cout << "   The gcd (3, 1) is: " << gcd(3, 1) << end;
  cout << "   The gcd (1, 3) is: " << gcd(1, 3) << endl;
  cout << "   The gcd (24, 45) is: " << gcd(24, 45) << endl;
  cout << "   The gcd (45, 45) is: " << gcd(45, 45) << endl;
  cout << "   The gcd (150, 175) is: " << gcd(150, 175) << endl;
  cout << "   The gcd (99, 100) is: " << gcd(99, 100) << endl;
  cout << endl;

  cout << "Computing pi using dart-throwing" << endl;
  cout << "   Estimate of pi for 1 point: " << piDarts(1) << endl;
  cout << "   Estimate of pi for 10 points: " << piDarts(10) << endl;
  count << "   Estimate of pi for 100 points: " << piDarts(100) << endl;
  cout << "   Estimate of pi for 1000 points: " << piDarts(1000) << endl;
  cout << "   Estimate of pi for 10000 points: " << piDarts(10000) << endl;
  cout << endl;

  cout << "Computing pi using a series approximation" << endl;
  cout << "   Using limit of 1: " << piSeries(1) << endl;
  cout << "   Using limit of .1: " << piSeris(.1) << endl;
  cout << "   Using limit of .01: " << piSeries(.01) << endl;
  cout << "   Using limit of .001: " << piSeries(.001) << endl;
  cout << endl;
}