Intel's Ronler Acres Plant

Silicon Forest

Tuesday, June 9, 2015

Pi from Nothin'

Riemann Hypothesis - Numberphile

Stu turned me on to an obscure little math trick for determining if a number is a prime number or not. It's not generally useful as it involves factorials, which get really big really fast. But there is a computer math package that can deal with numbers of any size, as long as you have enough computer memory to accommodate them, so I thought I would take Stu's formula and the GMP math package and see if I could make them play together.
     Dealing with really long numbers is not very difficult, you just have to keep track of overflows. Any half competent programmer should be able to write a set of routines to perform the basic operations, but it's a common enough job that some people got together and wrote a complete library of functions and procedures.
    Like any bit of software there are rules for how to use it. For me the easiest way to learn these rules is find a sample piece of code and start messing with it, so I went looking and I found this: randPi.c by Mitch Richling, which to purports to make Pi out of nothing but random numbers. He uses the GMP library to deal with his really long random numbers, so it was good example to start with. Plus it was weird. Pi from nothin'? How can that be?
     It depends on the observation that between any two random numbers, there is a statistical probability that they are relatively prime, i.e. the only factor they have in common is one. 3 and 4 are relatively prime. 3 and 6 are not, they have a factor of 3 in common. 4 and 6 are not, they have the factor 2 in common. Two numbers by themselves won't tell you much, but if you have big pile of them and start counting the number of pairs that are relatively prime and those that aren't, you end up with a ratio that (if you munge it just a bit) looks just like Pi.
    I got to thinking about this and realized you don't really need random numbers. After all, random numbers are just one number out of a range of numbers. You run long enough and you will cover all numbers in the range. You should be able to get the same effect by just testing the relative primeness of all the numbers in a range. I wrote a small program to test this and it indeed works. Running a cross tabulation of all the numbers from 1 to ten thousand resulted in value of 3.141534, which is not bad considering I made it from nothin'.

    Okay, we have GMP library and we think we know how to use it. Let's test Stu's formula, so I wrote another little program, it works and so Stu's formula seems to be valid. My program only goes up to 31, but that's only because we are starting to fill up the screen with the giant numbers that come from computing factorials. 31! (31 factorial) is like a zillion digits.

P.S. I have decided I don't like github because they don't handle tabs. Google Drive / Docs has a viewer that works okay and the two programs are stored there. It doesn't support highlighting, and there may be some argument over tabs, but it's not bad, and it doesn't require any extra fooling around.

1 comment:

Ole Phat Stu said...

Just as well I didn't mention Ackermann's function ;-)