# 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.