[QUIZ] Digits of Pi (#202)

D

Daniel Moore

-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2. Support Ruby Quiz by submitting ideas and responses
as often as you can!
Visit: <http://rubyquiz.strd6.com/suggestions>

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.

RSS Feed: http://rubyquiz.strd6.com/quizzes.rss

-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-

## Digits of Pi (#202)

Geia sas Rubyists,

Pi or =F0 is a mathematical constant whose value is the ratio of any
circle's circumference to its diameter in Euclidean space. Because =F0
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 =F0.

[1]: http://en.wikipedia.org/wiki/Pi

Have Fun!
--=20
-Daniel
http://rubyquiz.strd6.com
 
J

Joel VanderWerf

Daniel said:
This week's quiz is to write a Ruby program that can compute the first
100,000 digits of ð.

Bonus points for determining the first non-trivial ruby program encoded
in that sequence of digits.

(Represent a program source string as a sequence of octal triplets that
is, or is not, a subsequence of the octal representation of ð.)

Non-trivial means not "", not just a literal, etc. Be imaginative.
 
T

Todd Benson

2009/4/24 Joel VanderWerf said:
Bonus points for determining the first non-trivial ruby program encoded i= n
that sequence of digits.

Do you mean non-trivial in that it will never fail with the correct
initial conditions? Or simply that it's syntactically correct?
 
J

Joel VanderWerf

Todd said:
Do you mean non-trivial in that it will never fail with the correct
initial conditions? Or simply that it's syntactically correct?

I dunno. That's why I said be imaginative :)
 
J

Joel VanderWerf

Jeff said:
Interesting idea!

Is there any way of determining whether a given sequence of bytes is a
valid ruby program, other than running it? If this were my paternus
lingua, C++, I would start by chucking each candidate sequence at a
compiler.


What is an "octal triplet?" Do you mean that the integer value of each
byte in the source code should be represented by a sequence of three
octal digits (e.g. 077 for ?? and 141 for ?a)?

I'm curious: Why octal? It seems an odd choice, given that an "octal
triplet" corresponds to 9 bits, rather than the 8 in a standard byte.
Why not "hex pairs?"

You're right, that didn't make much sense. I was just thinking of "\nnn"
and counting to three, but of course that's 9 bits. What I was trying
to do was slice off just enough bits to make a printable char with high
probability. Otherwise, the 128..255 will keep breaking up otherwise
legal program strings.

Base 128 (7 bits) would be better, but there are still some non-printing
chars. Even better would be to skip ascii and use something else, but I
didn't want to get too far into fantasy land...
Btw, isn't every finite sequence of digits a subsequence of Pi's
representation in that base? Or is that unknowable?

IIRC that's true. But the _first_ ruby program... gee, that's got to
mean something. :)
 
R

Robert Dober

2009/4/27 Harry Kakueki said:
# Is this cheating ? =A0:)
I would say no, but...
I honestly could not come up with a solution, always getting confused
how many significant digits I need in the involved constants. Thus I
am really looking forward to the solutions and the summary. (Distant
memories tell me I should do some range arithmetics, we will see)
Sorry to say Harry, but your solution has not enlightened me on the topic ;=
).
Cheers
Robert
 
T

Todd Benson

2009/4/27 Robert Dober said:
I would say no, but...
I honestly could not come up with a solution, always getting confused
how many significant digits I need in the involved constants. Thus I
am really looking forward to the solutions and the summary. (Distant
memories tell me I should do some range arithmetics, we will see)
Sorry to say Harry, but your solution has not enlightened me on the topic= ;).
Cheers
Robert

For what it's worth, I tried a Gauss-Legendre and it halted my PC at a
delta of 1e-10 and smaller (only 10 good digits), and then started to
diverge pretty rapidly, so much so that the program would halt (yes, I
simply sat there and hit the gets over and over). I then tried
Srinavasa's method, and it converged so quickly to 10 places, and
never gave up after that, but it took about 3 hours to run k up to
1024 (without my intervention), which amounts to around 12_000 correct
places.

There's Daniel Shanks, which I might try my hand at eventually, but
the winner for this programming language might end up being
brute-force by-digit deterministic approach mentioned by one of the
first posters.

I think, Robert, cheating would be writing a program that grabs the
digits from the website :)

Todd
 
R

Robert Dober

2009/4/25 Joel VanderWerf said:
IIRC that's true. But the _first_ ruby program... gee, that's got to mean
something. :)

But that means that the representation of pi contains a ruby program
that computes pi itself (although of course it never finishes), and
that for any imaginable programming language capable of that task, eg
a TuringMachine.

I am confused now, but I bet the Ruby program starts exactly at the
42**42 hexdigit - for a well chosen base of course ;)
R.
 
R

Rick DeNatale

But that means that the representation of pi contains a ruby =A0program
that computes pi itself (although of course it never finishes), and
that for any imaginable programming language capable of that task, eg
a TuringMachine.


Been reading Goedel, Escher, Bach again, have we Robert? <G>
--=20
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale
 
A

Andy Cooper

[Note: parts of this message were removed to make it a legal post.]

I think, Robert, cheating would be writing a program that grabs the
digits from the website :)

Todd


I was unaware that one could cheat on a rubyquiz.
 
R

Robert Dober

Been reading Goedel, Escher, Bach again, have we Robert? <G>

To my defense I can claim: "I did not understand a bit", but it is
indeed a great read (actually never really finished it :-O )



--=20
Si tu veux construire un bateau ...
Ne rassemble pas des hommes pour aller chercher du bois, pr=E9parer des
outils, r=E9partir les t=E2ches, all=E9ger le travail=85 mais enseigne aux
gens la nostalgie de l=92infini de la mer.

If you want to build a ship, don=92t herd people together to collect
wood and don=92t assign them tasks and work, but rather teach them to
long for the endless immensity of the sea.
 
L

Luke Cowell

Here's a solution using the "plus/minus fractiony solution for pi" from
here:
http://tinyurl.com/3ve7wy

Note: this is also referred to as the Leibniz formula for pi


My solution is definitely not a great solution as after about 5 minutes,
I've got about 8 digits and it only gets slower. I doubt it will make it
to 100,000 digits. I'm looking forward to seeing other solutions to this
problem.

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
#puts current
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
 
C

Charles Oliver Nutter

Daniel said:
This week's quiz is to write a Ruby program that can compute the first
100,000 digits of π.

There's the impl on the benchmarks game (shootout):

http://shootout.alioth.debian.org/u32q/benchmark.php?test=pidigits&lang=ruby&id=1

But it doesn't seem fast enough to get to 100k digits in any amount of
time I'm willing to wait for it. Here's timings for all the Ruby
versions I have handy, calculating up to 10k digits:

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

Seems like we need a faster algorithm!

- Charlie
 
J

Jay Anderson

## Digits of Pi (#202)
This week's quiz is to write a Ruby program that can compute the first
100,000 digits of pi.

Attached is a solution using a machin formula
(http://en.wikipedia.org/wiki/Machin-like_formula) translated into ruby
from here:
http://en.literateprograms.org/Category:Pi_with_Machin's_formula.

$ time ruby pi.rb 100000 > pi.txt

real 1m44.592s
user 1m44.339s
sys 0m0.212s

No effort has been made to optimize, but it seems to have a reasonable
running time.

-----Jay

Attachments:
http://www.ruby-forum.com/attachment/3635/pi.rb
 
R

Robert Dober

The good new is that I chose the correct algorithm from the beginning.
The bad news is that I was waaaay to stupid to implement it, well
done.
BTW I tested your result, it seems to be correct :).
Cheers
Robert



--=20
Si tu veux construire un bateau ...
Ne rassemble pas des hommes pour aller chercher du bois, pr=E9parer des
outils, r=E9partir les t=E2ches, all=E9ger le travail=85 mais enseigne aux
gens la nostalgie de l=92infini de la mer.

If you want to build a ship, don=92t herd people together to collect
wood and don=92t assign them tasks and work, but rather teach them to
long for the endless immensity of the sea.
 
T

Todd Benson

The good new is that I chose the correct algorithm from the beginning.
The bad news is that I was waaaay to stupid to implement it, well
done.
BTW I tested your result, it seems to be correct :).
Cheers

Jay's version seemed to work fine. It took about 5 minutes on my
machine for 100_000.

I haven't verified the digits yet, though.

Todd
 
R

Robert Dober

Jay's version seemed to work fine. =A0It took about 5 minutes on my
machine for 100_000.

I haven't verified the digits yet, though.
I have ;)

Now that I learnt from Jay *not* to use BigDecimal :) I have
implemented Chen-Lih's machin formula,
last on this page: http://en.wikipedia.org/wiki/Machin-like_formula

But the speed gain is minimal 20~30% so that is definitely not worth
posting a *stolen* solution with this monster expression ;)
It run 70s instead of 97s (yes I have top notch hardware ;) for 100_000 dig=
its.

Cheers
Robert



--=20
Si tu veux construire un bateau ...
Ne rassemble pas des hommes pour aller chercher du bois, pr=E9parer des
outils, r=E9partir les t=E2ches, all=E9ger le travail=85 mais enseigne aux
gens la nostalgie de l=92infini de la mer.

If you want to build a ship, don=92t herd people together to collect
wood and don=92t assign them tasks and work, but rather teach them to
long for the endless immensity of the sea.
 
D

Daniel Moore

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 for calculating individua=
l%20hexadecimal%20digits%20of%20pi
[2]: http://en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_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's_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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,439
Members
44,829
Latest member
PIXThurman

Latest Threads

Top