202 Digits of Pi
Geia sas Rubyists,
Pi or π is a mathematical constant whose value is the ratio of any circle’s circumference to its diameter in Euclidean space. Because π is an irrational number, its decimal expansion never ends and does not repeat. This infinite sequence of digits has fascinated mathematicians and laymen alike, and much effort over the last few centuries has been put into computing more digits and investigating the number’s properties.1
This week’s quiz is to write a Ruby program that can compute the first 100,000 digits of π.
This week’s quiz sparked quite a discussion!
Dan Diebolt introduced the Bailey–Borwein–Plouffe formula (see also), a formula for computing the nth binary digit of π without computing the previous digits, though no solutions were provided that incorporated this formula.
Additionally, there was some talk of finding the first non-trivial Ruby program encoded in the digits of π, but choosing an appropriate encoding also proved to be non-trivial.
Harry Kakueki provided the first solution and made use of BigMath:
require 'bigdecimal' require 'bigdecimal/math' include BigMath puts PI(100_000)
Executing this solution took a little over five minutes on my machine. It is always good to know what libraries are already available.
Luke Cowell’s solution uses the Leibniz formula for pi.
require "rational" require 'enumerator' require 'bigdecimal' require 'bigdecimal/math' include BigMath iterations = 10000000000 current = 1 final = BigDecimal.new("4") other = false while(current < iterations) do current = current + 2 if(other) final = final + Rational(4,current) else final = final - Rational(4,current) end other = !other print current.to_s + ":" puts final.to_f end
Unfortunately, Leibniz’s formula is very inefficient for either mechanical or computer-assisted π calculation. Calculating π to 10 correct decimal places using Leibniz’ formula requires over 10,000,000,000 mathematical operations3. Luke stated on the mailing list this algorithm was only able to generate about eight digits in five minutes.
def arccot(x, unity) xpow = unity / x n = 1 sign = 1 sum = 0 loop do term = xpow / n break if term == 0 sum += sign * (xpow/n) xpow /= x*x n += 2 sign = -sign end sum end def calc_pi(digits = 10000) fudge = 10 unity = 10**(digits+fudge) pi = 4*(4*arccot(5, unity) - arccot(239, unity)) pi / (10**fudge) end digits = (ARGV || 10000).to_i p calc_pi(digits)
This solution produces 100k digits in around 2 minutes on my machine.
Robet Dober mentions a speed increase when using Hwang Chien-Lih’s Machin-like formula with additional terms:
pi = 4*(183*arccot(239, unity) + 32*arccot(1023, unity) - 68*arccot(5832, unity) + 12*arccot(110443, unity) - 12*arccot(4841182, unity) - 100*arccot(6826318, unity))
This does indeed improve the efficiency of the algorithm, I achieved 15-20% reduction in the time the algorithm took, down to about 100 seconds.
Charles Oliver Nutter pointed out the Ruby pidigits implementation on the Computer Language Benchmarks Game and provided some benchmarks for various Ruby implementations:
(jruby time is on Java 6 server VM) JRuby 1.3-dev: 0m47.903s Ruby 1.9.1: 1m27.527s Rubinius master: 2m50.545s MacRuby 0.4: 1m9.832s IKRuby*: 3m26.861s Ruby 1.8.7: 1m47.887s MacRuby 0.5-experimental crashed after only a few digits. IKRuby is JRuby on CLR (Mono, here) using IKVM.
These benchmarks only produced 10k digits of π (for expediency). One lesson to take away from this is that algorithm choice often has the biggest impact on performance.
10,000 Digits (Ruby 1.8.6 on my machine) Machin-like formula : ~ 1s BigMath : ~ 2.5s pidigits : ~ 1m30s Leibniz formula : ~ ?
And sometimes the fastest code is the code you don’t write. Michael Kohl’s solution:
require 'rubygems' require 'hpricot' require 'open-uri' doc = Hpricot(open('http://www.eveandersson.com/pi/digits/100000')) puts (doc/'pre').inner_html
It finishes in less than one second for the entire 100,000 digits!
Thank you everyone for your solutions and discussion! π is a timeless concept that has fascinated great minds for thousands of years and will continue to do so. If you are interested in learning more please follow the references as this summary barely scratches the surface. Thanks again to all who participated this week.
P.S. If you have any future quiz ideas be sure to submit them.