202 Digits of Pi

Description

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 π.

Summary

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.

Jay Anderson provided a solution using a Machin-like formula based on the implementation from the LiteratePrograms wiki:

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[0] || 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.

Saturday, April 25, 2009