-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 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 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ## Digits of Pi (#202) 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 ð. [1]: http://en.wikipedia.org/wiki/Pi Have Fun!

on 2009-04-24 23:05

on 2009-04-24 23:39

Daniel Moore wrote: > 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.

on 2009-04-25 03:05

>compute the first 100,000 digits of Ï€.What base do those digits have to be in? This algorithm allows you to calculate the n'th hexadecimal digit directly (without calculating the proceeding hexadecimal digits!): Algorithm for calculating individual hexadecimal digits of pi http://rubyurl.com/Zahp

on 2009-04-25 03:30

Joel VanderWerf wrote: > Daniel Moore wrote: >> 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. 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. > (Represent a program source string as a sequence of octal triplets > that is, or is not, a subsequence of the octal representation of ð.) 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?" Btw, isn't every finite sequence of digits a subsequence of Pi's representation in that base? Or is that unknowable?

on 2009-04-25 04:54

2009/4/24 Joel VanderWerf <vjoel@path.berkeley.edu>: > Daniel Moore wrote: >> >> 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. Do you mean non-trivial in that it will never fail with the correct initial conditions? Or simply that it's syntactically correct?

on 2009-04-25 04:58

Todd Benson wrote: > 2009/4/24 Joel VanderWerf <vjoel@path.berkeley.edu>: >> Daniel Moore wrote: >>> 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. > > 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 :)

on 2009-04-25 05:13

Jeff Schwab wrote: > valid ruby program, other than running it? If this were my paternus > 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. :)

on 2009-04-27 03:10

> > This week's quiz is to write a Ruby program that can compute the first > 100,000 digits of ð. > > # Is this cheating ? :) require 'bigdecimal' require 'bigdecimal/math' include BigMath puts PI(100_000) Harry

on 2009-04-27 07:50

2009/4/27 Harry Kakueki <list.push@gmail.com>: >> >> This week's quiz is to write a Ruby program that can compute the first >> 100,000 digits of ð. >> >> > > # Is this cheating ? :) 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

on 2009-04-27 08:14

2009/4/27 Robert Dober <robert.dober@gmail.com>: > 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

on 2009-04-27 15:16

2009/4/25 Joel VanderWerf <vjoel@path.berkeley.edu>: >> 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. :) 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.

on 2009-04-27 15:21

Robert Dober wrote: > 2009/4/25 Joel VanderWerf <vjoel@path.berkeley.edu>: >>> 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. :) > > 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. Infinite is biiiiiiiig... > I am confused now, but I bet the Ruby program starts exactly at the > 42**42 hexdigit - for a well chosen base of course ;) "You may think it's a long walk to the chemist, but that's just peanuts to space."

on 2009-04-27 15:30

On Mon, Apr 27, 2009 at 9:15 AM, Robert Dober <robert.dober@gmail.com> wrote: > a TuringMachine. Been reading Goedel, Escher, Bach again, have we Robert? <G> -- 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

on 2009-04-27 15:33

On Mon, 2009-04-27 at 15:12 +0900, Todd Benson wrote: > > 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.

on 2009-04-27 15:48

On Mon, Apr 27, 2009 at 3:27 PM, Rick DeNatale <rick.denatale@gmail.com> wrote: >> that for any imaginable programming language capable of that task, eg >> a TuringMachine. > > > Been reading Goedel, Escher, Bach again, have we Robert? <G> > -- > Rick DeNatale 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 ) > > 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 > > -- Si tu veux construire un bateau ... Ne rassemble pas des hommes pour aller chercher du bois, préparer des outils, répartir les tâches, alléger le travail… mais enseigne aux gens la nostalgie de l’infini de la mer. If you want to build a ship, don’t herd people together to collect wood and don’t assign them tasks and work, but rather teach them to long for the endless immensity of the sea.

on 2009-04-27 17:53

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

on 2009-04-29 05:33

Hi Pi is a variable number which changes with different radii. PI can be 3.12 or 3.45.... Please see the proof of variable PI: http://www.lecan.net/raremath.html Good luck Can Le --- On Mon, 4/27/09, Jeff Schwab <jeff@schwabcenter.com> wrote: From: Jeff Schwab <jeff@schwabcenter.com> Subject: Re: [QUIZ] Digits of Pi (#202) To: "ruby-talk ML" <ruby-talk@ruby-lang.org> Date: Monday, April 27, 2009, 8:20 AM Robert Dober wrote: > 2009/4/25 Joel VanderWerf <vjoel@path.berkeley.edu>: >>> 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. :) > > 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. Infinite is biiiiiiiig... > I am confused now, but I bet the Ruby program starts exactly at the > 42**42 hexdigit - for a well chosen base of course ;) "You may think it's a long walk to the chemist, but that's just peanuts to space."

on 2009-04-29 06:24

On Tue, Apr 28, 2009 at 10:32 PM, Can Le <lecan75228@yahoo.com> wrote: > > > http://www.lecan.net/raremath.html > > > > Good luck I'm sorry, but maybe I'm missing something. Aren't you just restating the "many-polygon becomes a circle" problem? Good luck, indeed! I must have been thinking about something else :) Todd

on 2009-04-29 07:01

> I'm sorry, but maybe I'm missing something. Aren't you just restating > the "many-polygon becomes a circle" problem? Good luck, indeed! I > must have been thinking about something else :) That was a bit unfair. I thought you were talking about something else. Todd

on 2009-04-29 16:24

2009/4/27 Harry Kakueki <list.push@gmail.com>: > # Is this cheating ? :) I guess the only thing I'd consider cheating would be something like this: require 'rubygems' require 'hpricot' require 'open-uri' doc = Hpricot(open('http://www.eveandersson.com/pi/digits/100000')) puts (doc/'pre').inner_html Michael

on 2009-04-29 18:21

Daniel Moore wrote: > 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.p... 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

on 2009-04-30 05:02

> ## 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_Ma.... $ 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

on 2009-04-30 14:21

On Thu, Apr 30, 2009 at 5:02 AM, Jay Anderson <horndude77@gmail.com> wrote: 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 -- Si tu veux construire un bateau ... Ne rassemble pas des hommes pour aller chercher du bois, préparer des outils, répartir les tâches, alléger le travail… mais enseigne aux gens la nostalgie de l’infini de la mer. If you want to build a ship, don’t herd people together to collect wood and don’t assign them tasks and work, but rather teach them to long for the endless immensity of the sea.

on 2009-04-30 22:23

On Thu, Apr 30, 2009 at 7:21 AM, Robert Dober <robert.dober@gmail.com> wrote: > On Thu, Apr 30, 2009 at 5:02 AM, Jay Anderson <horndude77@gmail.com> wrote: > 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

on 2009-04-30 23:16

On Thu, Apr 30, 2009 at 10:21 PM, Todd Benson <caduceass@gmail.com> wrote: > > 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 digits. Cheers Robert > > Todd > > -- Si tu veux construire un bateau ... Ne rassemble pas des hommes pour aller chercher du bois, préparer des outils, répartir les tâches, alléger le travail… mais enseigne aux gens la nostalgie de l’infini de la mer. If you want to build a ship, don’t herd people together to collect wood and don’t assign them tasks and work, but rather teach them to long for the endless immensity of the sea.

on 2009-05-03 02:55

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 ð 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[3]. 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 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 = 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[6]: 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[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 ð (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. [1]: http://everything2.com/title/Algorithm%20for%20cal... [2]: http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwei... [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_Ma... [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.p... P.S. If you have any future quiz ideas be sure to submit them: http://rubyquiz.strd6.com/suggestions.