|Re: Pi day - Calculate Pi on your 15C|
Message #17 Posted by Egan Ford on 15 Mar 2007, 5:11 p.m.,
in response to message #16 by Palmer O. Hanson, Jr.
I first encountered this method in Using MPI. MPI is the standard for parallel programming distributed memory supercomputers (a.k.a superclusters). As you can imagine 100s, 1000s, or 10s of 1000s of high-speed processors generating random numbers in parallel will crank out Pi to 10 digits much faster. Not surprisingly it still can take a relatively long time (a proper deterministic algorithm on a 15C will still best it). If you're ever interested in exploring the other side of the scientific computing spectrum, pick up this book, a cheap switch, a few cheap PCs, and Linux.
The Linux random number generator utilizes entropy to increase its randomness. Entropy sources include keyboard and mouse usage, disk I/O, and system interrupts. I have never tested how random this is, but it should be easy to test by simply generating a series of random bits and then trying to compress it.
Entropy should be possible on some calculators. The 50G should be able to create an entropy pool over time based on keystrokes, battery voltage, I/O, etc... Perhaps the 50G does this today. Probably not, it is unimportant for a handheld calculator to have a robust random number generator. Random numbers in Linux are critical for security. If I want to secure my 50G I'll just lock it in my office or car.
Back to the 15C. Instead of using random numbers we can assume that we have a random number generator with a perfect uniform distribution and at the same time we will assume that all numbers are generated at least once first before reoccurring similar to shuffling a deck of cards.
The smallest fraction that will generate Pi/4 is:
If we generate 2e9 points with an even distribution from 0,0 to 1,1 then we should get Pi faster by simulating the uniform distribution of the inevitable if we had a true random distribution. Points for x and y will range from 0 to 1 step 1/sqrt(2e9).
At 2 sec/iteration generating the 10 digits of Pi will only take ~ 126.75 years.