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)

Permalink