This week’s quiz sparked quite a discussion!
Dan D. introduced the Bailey-Borwein-Plouffe formula1, 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 K. 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 C.'s solution uses the Leibniz formula for pi3.
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 A. provided a solution using a Machin-like formula4 based
on the implementation from the LiteratePrograms wiki5:
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 terms6:
pi = 4*(183*arccot(239, unity) + 32*arccot(1023, unity) -
68arccot(5832, unity) + 12arccot(110443, unity) - 12arccot(4841182,
unity) - 100arccot(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 N. pointed out the Ruby pidigits implementation on
the Computer Language Benchmarks Game7 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:
http://rubyquiz.strd6.com/suggestions.
I have