How do they calculate Pi?

Factual Questions
1

Every now and then, I hear about scientists and their New Super-Duper Computer that calculates pi to a trillion decimal places or so. But my question is, how? To calculate something, there has to be a formula, right? The closest thing to a “formula” I’ve ever seen was 22/7, but to my recollection that has a finite end shortly after calculating 3.14 (well, okay, it starts repeating shortly after).

So what do scientists do to calculate pi? Do they just type “pi” into their calculator and press Enter? Do they have some giant Perfect Circle in a lab somewhere that they just look at with finer and finer scanning devices? Or do they just throw new random numbers on the end, figuring that none of the Little People of the world will ever be able to check?

I guess what I’m asking is… if I wanted to calculate pi, starting with no prior knowledge, what numbers and equations will I have to put in to figger it out?

2

The three major methods are discussed here.

3

22/7 is an approximation for pi.

There are a number of formulas which allow you to calculate pi. One of the most famous, and most simple, is (pi)/4 = 1 - 1/3 + 1/5 - 1/7…That formula (and about a million others) will get you any number of digits of pi. Computer scientists do not usually use this formula, as it converges very slowly, but the ones they do use are extremely similar – they are the sum of a bunch of terms, each one getting closer to the true value of pi.

Several dozen formulas for pi can be found here.

4

A simple, intuitive method is as follows:

  1. Generate a bunch of random number pairs (x,y) where both x and y are between -1 and 1, e.g. (0.183247827497,0.99284738472).
  2. These numbers will always be inside a square on the x-y plane (area=4). However, some of them will also be inside a circle of radius 1 centered at (0,0).
  3. Because the area of a circle is pi*radius[sup]2[/sup] by definition, the fraction of random number pairs which are inside the circle will be pi/4. The more random number pairs you generate, the more accurately you’ll calculate pi.

This is not the most efficient method, but you could write a program to do it in about five lines, so it’s probably the most simple.

5

I just tried it and although it was simple, it converges very slowly. This may be caused by bad programming, but after 100,000 pairs I got a value of about 3.13528 for pi.

6

Well, he did say it wasn’t the most efficient method possible. Heh.

7

I applaud you on this, it is indeed simple, intuitive, and elegant. (To me, at least.)

How do you tell whether or not a dot is inside or outside the circle? My guess is that if X[sup]2[/sup]+Y[sup]2[/sup] > 1 then it is outside the circle, and if X[sup]2[/sup]+Y[sup]2[/sup] < 1 this it is inside. What do you do for the rare case where it equals one?

8

Since the circle we’re dealing with is defined as having a radius of 1, then if a point is “on the line” at 1 exactly, it would be inside the circle.

9

Since the circle we’re dealing with is defined as having a radius of 1, then if a point is “on the line” at 1 exactly, it would be inside the circle.

So the inequalities should be:

Inside: X[sup]2[/sup] + Y[sup]2[/sup] <= 1
Outside: X[sup]2[/sup] + Y[sup]2[/sup] > 1

10

No, I would expect it to converge very slowly. Also, 100,000 pairs is actually not very many random numbers for a calculation of this sort.

And friedo was right about the circle. It doesn’t really matter – the difference between 0.999999999999 and 1.000000000000 is small.

11

Here is a version of The Giraffe Method that I just wrote in Perl:



#!/usr/bin/perl

use strict;

print "How many points? ";
my $total = <STDIN>;

my $in;
my $out;

for(1..$total) {
        my $x = (rand 2) - 1;
        my $y = (rand 2) - 1;

        my $hyps = (($x ** 2) + ($y ** 2));
        my $hyp = sqrt($hyps);

        if ($hyp <= 1) { $in++ }
        elsif ($hyp > 1) { $out++ }
}

my $distr = $in / $total;
print "Points generated: $total
";
print "Points inside: $in
";
print "Points outside: $out
";
print "Points distribution ratio (pi/4):  $distr
";
print "Pi: ", $distr * 4, "
";

And here’s some sample output:



[24-90-225-158:~] friedo% perl pi.pl
How many points? 1000000
Points generated: 1000000

Points inside: 784628
Points outside: 215372
Points distribution ratio (pi/4):  0.784628
Pi: 3.138512
[24-90-225-158:~] friedo% perl pi.pl
How many points? 10000000
Points generated: 10000000

Points inside: 7853322
Points outside: 2146678
Points distribution ratio (pi/4):  0.7853322
Pi: 3.1413288
12

Are you sure? My first instinct is that the set of points where x^2 + y^2 = 1 have a total area of zero, meaning that it wouldn’t matter whether you consider it as in or out. I have long forgotten the math (if I ever knew it) to prove this intuition, however.

13

The set of points may have an area of zero, but they are the boundary of the shape we are interested in, which is a circle with radius 1. So they should be counted along with all the other random points that land inside the circle.

14

I fail to see that, friedo.

Logically, how can you state that the figure that determines the figure can be either definitevely inside or outside the circle? I don’t see why one assertion is valid than the other.

Mathematically, I don’t see why it would matter.

15

The definition of a circle is

The area of a circle with r = 1 includes all points that are 1 unit away from O and all points bounded by that shape. If you exclude those points, then you have a circle with radius 0.999…, which is different than a circle with radius of 1. If you don’t believe me, see the example of deriving the area of a circle through integration (33) on the page linked above.

16

But 0.999… is equal to 1. :smiley:

(I think you meant 0.999…9, if that’s even a proper method of expressing the idea.)

Anyway, thanks for the replies… now if I ever get transported back to prehistoric times, I can REALLY muck up the history of mathematics!

17

Didn’t we just cover this a few weeks ago with Cecil’s column?

0.999… is exactly 1.

I might have been whooshed. I’m reading from a text-mode browser, so if you put a smiley in your last post, friedo, I probably missed it.

18

Yes, yes yes. I meant slightly less than one. Friedo stupid. My bad.

19

In this thread Orbifold posted a link to a page having lots of formulae. I posted Borwein’s algorithm.

20

15 or more years ago, a buddy of mine was playing around with a computer that was prett fast (it had a Motorola 68030 IIRC), so I challenged him to make it calculate pi faster than my HP 41C calculator, using the formula pi = 4/1 - 4/3 + 4/5 - 4/7…

He gladly accepted the challenge. After several hours, he had five digits. He let it run over the weekend and had six. I showed him the program running on my 41C, which converged to all ten displayed digits in about 60 seconds.

The difference was that I was playing around with the formula, and noticed that after several terms, the sum bounced around a little bit above pi, then a little below. So I started keeping track of the average of the last two terms. This sequence was very much closer to pi, but it still bounced around above and below. So I averaged the last two averages. That number was way closer still, but it still bouned above and below. I next took the average ten levels deep. This is the one that converged to ten digits in 60 seconds. And the 41C was really really slow at this kind of stuff. I’m sure it was less than 100 terms that it took to get there. I’d like to see a perl script or a C program to do this on a fast computer!