Sunday, October 22, 2017
By: Matthew Doucette
Last night, I wrote a quick program to estimate Pi via random numbers.
Random Pi running up to 100,000,000,000 iterations.
Algorithm:
The idea is to randomly choose (x,y) points within the unit cube (-1.0..1.0,-1.0..1.0) and measure the percentage of points lying inside the unit sphere. Using the area of a circule formula -- area = pi * radius^2 -- you can deduce the inside:total ratio multiplied by 4 is Pi.
This is known as the Monte Carlo method.
Results:
On my first run, after 114,880,000,000 random points, Pi was estimated to be 3.1415975457520893, which is off by 0.00000489216, or 0.00015572236%.
On a second run, using v2.0, after 5,144,300,000,000 random points, Pi was estimated to be 3.1415924060968452, which is off by 0.000000247492948, or 0.00000787794%.
Stats:
- v1 = 37,260,672.4 pts/s
- v2 = 57,789,967.0 pts/s = 1.55x faster than v1
- v3 = 58,756,541.3 pts/s = 1.02x faster than v2 = 1.58x faster than v1
- v4 = 66,119,348.1 pts/s = 1.13x faster than v3 = 1.77x faster than v1
- v5 = 92,575,635.3 pts/s = 1.40x faster than v4 = 2.48x faster than v1
Speeds are measured by average after 1 minute of calculation, on my gaming laptop:
- ASUS - Republic of Gamers
- Microsoft Windows 10 Home
- Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz, 2594 Mhz, 4 Core(s), 8 Logical Processor(s)
- 16.0 GB RAM
- 64-bit O/S, x64-based processor
Optimizations:
- v1.0:
-
- I calculate quarter of unit cube only, from (0.0..1.0, 0.0..1.0), to coincide with random number generator results (0.0..1.0) and remove the need to scale to -1.0..1.0.
- This optimization was minimal in performance increase.
- v2.0:
-
- I made double use of each random number generator result, by using it for both x and y, but not at the same time. For each new point, the x-value is derived from the previous point's y-value, and the y-value is calculated brand new via the random number generator.
- This was a 1.55x speed increase as the random number generation is what takes most of the time to calculate.
- v3.0:
-
- Only calculate Pi during output, not for each random point calculated. So, it calculates lots of points and stores the total, but only solves for Pi when the program creates an output, which saves 10,000,000 calculations of Pi (multiplies by 4) per each output line.
- Minimal improvement in speed.
- v4.0:
-
- Removed a coversion to double that was unnecessary. No idea why this sped up the program at all. Could be the optimizing compiler or the code being smaller and fitting into cache while in the loop or something.
- v5.0:
-
- A cool optimization, addressing that the random number generator is what is slow:
- Construct two random numbers from each single generated random number, using bit manipulations, via "C++ unions" in C# via StructLayout(LayoutKind.Explicit) and FieldOffset attributes to create equivalent functionality. Creating a new random number this way is faster than generating a new random number via the generator.
- A warning is to only affect the mantissa, not sign-bit or exponent, to maintain 0.0..1.0 range.
- 1.40x faster.
Any more ideas? Let me know!
Video:
Random Pi v1.0 (PC) - Estimating Pi with Random Numbers
Inspiration:
"Random Pi" was inspired by the following video by Physics Girl and Veritasium:
Calculating Pi with Darts
2017-NOV-06 UPDATE:
Check out Not-So-Random Pi.
Check out our other prototype work if you wish.
That is all.
About the Author: I am Matthew Doucette of Xona Games, an award-winning indie game studio that I founded with my twin brother. We make intensified arcade-style retro games. Our business, our games, our technology, and we as competitive gamers have won prestigious awards and received worldwide press. Our business has won $190,000 in contests. Our games have ranked from #1 in Canada to #1 in Japan, have become #1 best sellers in multiple countries, have won game contests, and have held 3 of the top 5 rated spots in Japan of all Xbox LIVE indie games. Our game engines have been awarded for technical excellence. And we, the developers, have placed #1 in competitive gaming competitions -- relating to the games we make. Read about our story, our awards, our games, and view our blog.