# 11.20.06

## An unusual way to calculate Pi

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)*

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.