[QUIZ][SUMMARY] Digits of Pi (#202)

This week's quiz sparked quite a discussion!

Dan Diebolt introduced the Bailey-Borwein-Plouffe formula[1][2], a
formula for computing the nth binary digit of =F0 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 =F0, 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[3].

    require "rational"
    require 'enumerator'
    require 'bigdecimal'
    require 'bigdecimal/math'
    include BigMath

    iterations =3D 10000000000
    current =3D 1
    final =3D BigDecimal.new("4")
    other =3D false

    while(current < iterations) do
      current =3D current + 2
      if(other)
        final =3D final + Rational(4,current)
      else
        final =3D final - Rational(4,current)
      end

      other =3D !other
      print current.to_s + ":"
      puts final.to_f
    end

Unfortunately, Leibniz's formula is very inefficient for either
mechanical or computer-assisted =F0 calculation. Calculating =F0 to 10
correct decimal places using Leibniz' formula requires over
10,000,000,000 mathematical operations[3]. 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[4] based
on the implementation from the LiteratePrograms wiki[5]:

    def arccot(x, unity)
        xpow =3D unity / x
        n =3D 1
        sign =3D 1
        sum =3D 0
        loop do
            term =3D xpow / n
            break if term =3D=3D 0
            sum +=3D sign * (xpow/n)
            xpow /=3D x*x
            n +=3D 2
            sign =3D -sign
        end
        sum
    end

    def calc_pi(digits =3D 10000)
        fudge =3D 10
        unity =3D 10**(digits+fudge)
        pi =3D 4*(4*arccot(5, unity) - arccot(239, unity))
        pi / (10**fudge)
    end

    digits =3D (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[6]:

    pi =3D 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[7] 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 =F0 (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 =3D 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! =F0 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.

[1]: http://everything2.com/title/Algorithm%20for%20calculating%20individua=
l%20hexadecimal%20digits%20of%20pi
[2]: http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_fo=
rmula
[3]: http://en.wikipedia.org/wiki/Leibniz_formula_for_pi
[4]: http://mathworld.wolfram.com/Machin-LikeFormulas.html
[5]: http://en.literateprograms.org/Category:Pi_with_Machin%27s_formula
[6]: http://en.wikipedia.org/wiki/Machin-like_formula#More_terms (It
appears that this Wikipedia article is displaying arctan instead of
arccot)
[7]: http://shootout.alioth.debian.org/u32q/benchmark.php?test=3Dpidigits&l=
ang=3Druby&id=3D1

P.S. If you have any future quiz ideas be sure to submit them:
http://rubyquiz.strd6.com/suggestions.

--=20
-Daniel
http://rubyquiz.strd6.com