11.20.06

An unusual way to calculate Pi

Posted in programming at 12:17 am by danvk

Can you figure out how this program does it?

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

unsigned int gcd (unsigned int a, unsigned int b)
{
  while (b) {
    unsigned int c = b;
    b = a % b;
    a = c;
  }
  return a;
}

int main(int argc, char** argv) {
  if (argc != 2) {
    fprintf(stderr, "Usage: %s <sample size>\n", argv[0]);
    exit(1);
  }
  
  unsigned int sample_size = atol(argv[1]);
  unsigned int count = 0;
  srand(time(NULL));

  for (unsigned int i=0; i<sample_size; i++) {
    unsigned int a = rand();
    unsigned int b = rand();

    if (gcd(a,b) == 1)
      count++;
  }

  double pi = sqrt(6.0 * sample_size / count);
  printf("%d: %.6f - %.6f = %.6f\n",
          sample_size, pi, M_PI, fabs(pi-M_PI));
}

Convergence is pretty bad, probably O(sqrt(log N)), but it’s cool that it works!

Input Runtime |Output-π| = Error
1,000 0.001s |3.170213 – 3.141593| = 0.028620
10,000 0.003s |3.119420 – 3.141593| = 0.022173
100,000 0.025s |3.142490 – 3.141593| = 0.006862
1,000,000 0.243s |3.140774 – 3.141593| = 0.000818
10,000,000 2.427s |3.141377 – 3.141593| = 0.000216
100,000,000 24.256s |3.141756 – 3.141593| = 0.000164
1,000,000,000 242.518s |3.141692 – 3.141593| = 0.000099

(Thanks to C++2HTML for the syntax coloring)

1 Comment

  1. Craig Fratrik said,

    November 20, 2006 at 7:04 am

    I’ve heard really bad things about the C random number generator, I wonder if they affect this and if a different one would perform better.