6 ms·

Pi Formulas, Algorithms and Computations (2009)

98 points by h2odragon 5y ago

edf13 5y ago
Bad SSL cert on the www. Work on: https://bellard.org/pi/ https://bellard.org/pi/
- enriquto 5y ago
  This may be some sort of elaborate trolling on his part.
  - deleted 5y ago
    [deleted]
- blueflow 5y ago
  If the mods could fix the link? Maybe a @dang does summon them.
- tlb 5y ago
  Fixed, thanks
amelius 5y ago
What is the fastest algorithm to find a given substring in the digits of Pi?
- loa_in_ 5y ago
  Brute force E: if you want to have reliable, consistent results that is
  - Someone 5y ago
    Depends on what you call brute force. I think what one should call the brute force method is either the approximation by inscribed and circumscribed polygons (https://www.geogebra.org/m/BhxyBJUZ https://www.geogebra.org/m/BhxyBJUZ) or https://en.wikipedia.org/wiki/Leibniz_formula_for_π https://en.wikipedia.org/wiki/Leibniz_formula_for_π, https://en.wikipedia.org/wiki/Madhava_of_Sangamagrama#The_value_of_π_(pi) https://en.wikipedia.org/wiki/Madhava_of_Sangamagrama#The_va... The much faster algorithms known today still require lots of force, but I wouldn’t call them brute force. If the search string is long, it might even be faster to not generate each digit, but use (a variant of) Boyer-Moore to do the search (https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algo...) I guess “long” would have to very long for that to be profitable, though. There also is no known algorithm to do that that is known to terminate (if π is normal, they would, but we don’t know whether it is)
- dolmen 5y ago
  It depends on the range of the index and how often you want that data. If the position is below 5 trillion, you might want to calculate them once with Bellard's software and use that data.
h2odragon 5y ago
Apologies for the bad link. Also: https://github.com/philipl/pifs https://github.com/philipl/pifs
- edf13 5y ago
  Nice! > Every file that could possibly exist? > That's right! Every file you've ever created, or anyone else has created or will create! Copyright infringement? It's just a few digits of π! They were always there! How about prior-art for Patents? Every invention is already written in Pi!
jzer0cool 5y ago
In layman's term, how did one discover this series which generates the pi digit patterns?
- loa_in_ 5y ago
  Lots and lots and lots of experimentation (experimentation on paper) and looking out for clever ways to find parts of the equation-at-hand that cancel each other out, so that the resulting notation is hopefully as short and practical as the equation is good at being accurate.
- abetusk 5y ago
  Judicious use of lattice reduction techniques such as LLL [0] or other integer relation algorithms, like PSLQ [1]. The basic idea with LLL is that it's a sort of generalized Euclid's algorithm. Euclid's algorithm can be made to find the smallest integer relation between two numbers that sums to zero (efficiently). You can generalize Euclid's algorithm to more numbers and to use vectors instead of base integers, except now the "divide, take the integer quotient and subtract" becomes "take off the integral component of the projection and subtract, then swap entries to try and make progress". Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials with integral coefficients). To use lattice reduction techniques, you set up a "lattice basis" that has successive powers of pi (pi^0, pi^1, pi^2 etc) up to a certain accuracy and then tries to find an integer relation between them. Once one is found, it's checked to see if it actually equals pi by other techniques. For an introduction to LLL, I've found Chee Yap's book to be good (see chapter VIII) [2]. Plouffe has a little bit of history about the discovery and how Bailey and Borwein muscled in [3]. [0] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%... [1] https://en.wikipedia.org/wiki/Integer_relation_algorithm https://en.wikipedia.org/wiki/Integer_relation_algorithm [2] http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental%20Problems%20in%20Algorithmic%20Algebra%201993%20Yap.pdf http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental... [3] http://xahlee.info/math/Simon_Plouffe_pi_formula.html http://xahlee.info/math/Simon_Plouffe_pi_formula.html
omginternets 5y ago
Long live Tau, long live Tau! https://treelight.com/essays/ideas/the-way-of-the-tau-better-than-pi/ https://treelight.com/essays/ideas/the-way-of-the-tau-better...
- nh23423fefe 5y ago
  This is like a weaker version of master to main.
umvi 5y ago
FYI for those unaware - Bellard (the author of the article) is also the author of ffmpeg and qemu.
- isaacimagine 5y ago
  And tcc, and quickjs, and tinygl, and... Honestly his output is insane in terms of both quality and quantity. There's a list of his projects on his homepage (https://bellard.org https://bellard.org).
- paulpauper 5y ago
  this guy is the epitome of computer science (along with Knuth)
tvb 5y ago
With a nod to fellow pi-hound Dik T Winter, three equal lines of C give 32k digits of pi: http://leapsecond.com/tools/pi3.c http://leapsecond.com/tools/pi3.c
- jeffwass 5y ago
  brilliant method of embedding his name in the code without wasting lines for comments
  - divbzero 5y ago
    “…signed by Dik T Winter”
    - tvb 5y ago
      You can grep the web for Dik's original version. The 3-line homage version I linked contains both his full name and the name of the algorithm used: "spigot" (as in spew, faucet), which itself contains the letters PI. In addition, this version outputs exactly 31416 digits of pi. So it's triple self-referential. Happy 2022.03.14 pi day to all.
      - zodzedzi 5y ago
        Which spigot algorithm is the 3-line version using exactly? (I did some untangling of the code in limited time, but it's still pretty cryptic.)
        tvb 5y ago
        The original pi/spigot work was done by Rabinowitz & Wagon [1]. See also the very readable works by Jeremy Gibbons [2] [3]. [1] https://en.wikipedia.org/wiki/Spigot_algorithm https://en.wikipedia.org/wiki/Spigot_algorithm [2] https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/s... [3] https://seminar-materials.iijlab.net/iijlab-seminar/iijlab-seminar-20170327.pdf https://seminar-materials.iijlab.net/iijlab-seminar/iijlab-s...

98 points by h2odragon 5y ago

edf13 5y ago

Bad SSL cert on the www. Work on: https://bellard.org/pi/ https://bellard.org/pi/

enriquto 5y ago
This may be some sort of elaborate trolling on his part.
- deleted 5y ago
  [deleted]
blueflow 5y ago
If the mods could fix the link? Maybe a @dang does summon them.
tlb 5y ago
Fixed, thanks

amelius 5y ago

What is the fastest algorithm to find a given substring in the digits of Pi?

loa_in_ 5y ago
Brute force E: if you want to have reliable, consistent results that is
- Someone 5y ago
  Depends on what you call brute force. I think what one should call the brute force method is either the approximation by inscribed and circumscribed polygons (https://www.geogebra.org/m/BhxyBJUZ https://www.geogebra.org/m/BhxyBJUZ) or https://en.wikipedia.org/wiki/Leibniz_formula_for_π https://en.wikipedia.org/wiki/Leibniz_formula_for_π, https://en.wikipedia.org/wiki/Madhava_of_Sangamagrama#The_value_of_π_(pi) https://en.wikipedia.org/wiki/Madhava_of_Sangamagrama#The_va... The much faster algorithms known today still require lots of force, but I wouldn’t call them brute force. If the search string is long, it might even be faster to not generate each digit, but use (a variant of) Boyer-Moore to do the search (https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algo...) I guess “long” would have to very long for that to be profitable, though. There also is no known algorithm to do that that is known to terminate (if π is normal, they would, but we don’t know whether it is)
dolmen 5y ago
It depends on the range of the index and how often you want that data. If the position is below 5 trillion, you might want to calculate them once with Bellard's software and use that data.

h2odragon 5y ago

Apologies for the bad link. Also: https://github.com/philipl/pifs https://github.com/philipl/pifs

edf13 5y ago
Nice! > Every file that could possibly exist? > That's right! Every file you've ever created, or anyone else has created or will create! Copyright infringement? It's just a few digits of π! They were always there! How about prior-art for Patents? Every invention is already written in Pi!

jzer0cool 5y ago

In layman's term, how did one discover this series which generates the pi digit patterns?

loa_in_ 5y ago
Lots and lots and lots of experimentation (experimentation on paper) and looking out for clever ways to find parts of the equation-at-hand that cancel each other out, so that the resulting notation is hopefully as short and practical as the equation is good at being accurate.
abetusk 5y ago
Judicious use of lattice reduction techniques such as LLL [0] or other integer relation algorithms, like PSLQ [1]. The basic idea with LLL is that it's a sort of generalized Euclid's algorithm. Euclid's algorithm can be made to find the smallest integer relation between two numbers that sums to zero (efficiently). You can generalize Euclid's algorithm to more numbers and to use vectors instead of base integers, except now the "divide, take the integer quotient and subtract" becomes "take off the integral component of the projection and subtract, then swap entries to try and make progress". Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials with integral coefficients). To use lattice reduction techniques, you set up a "lattice basis" that has successive powers of pi (pi^0, pi^1, pi^2 etc) up to a certain accuracy and then tries to find an integer relation between them. Once one is found, it's checked to see if it actually equals pi by other techniques. For an introduction to LLL, I've found Chee Yap's book to be good (see chapter VIII) [2]. Plouffe has a little bit of history about the discovery and how Bailey and Borwein muscled in [3]. [0] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%... [1] https://en.wikipedia.org/wiki/Integer_relation_algorithm https://en.wikipedia.org/wiki/Integer_relation_algorithm [2] http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental%20Problems%20in%20Algorithmic%20Algebra%201993%20Yap.pdf http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental... [3] http://xahlee.info/math/Simon_Plouffe_pi_formula.html http://xahlee.info/math/Simon_Plouffe_pi_formula.html

omginternets 5y ago

Long live Tau, long live Tau! https://treelight.com/essays/ideas/the-way-of-the-tau-better-than-pi/ https://treelight.com/essays/ideas/the-way-of-the-tau-better...

nh23423fefe 5y ago
This is like a weaker version of master to main.

umvi 5y ago

FYI for those unaware - Bellard (the author of the article) is also the author of ffmpeg and qemu.

isaacimagine 5y ago
And tcc, and quickjs, and tinygl, and... Honestly his output is insane in terms of both quality and quantity. There's a list of his projects on his homepage (https://bellard.org https://bellard.org).
paulpauper 5y ago
this guy is the epitome of computer science (along with Knuth)

tvb 5y ago

With a nod to fellow pi-hound Dik T Winter, three equal lines of C give 32k digits of pi: http://leapsecond.com/tools/pi3.c http://leapsecond.com/tools/pi3.c

jeffwass 5y ago
brilliant method of embedding his name in the code without wasting lines for comments
- divbzero 5y ago
  “…signed by Dik T Winter”
  - tvb 5y ago
    You can grep the web for Dik's original version. The 3-line homage version I linked contains both his full name and the name of the algorithm used: "spigot" (as in spew, faucet), which itself contains the letters PI. In addition, this version outputs exactly 31416 digits of pi. So it's triple self-referential. Happy 2022.03.14 pi day to all.
    - zodzedzi 5y ago
      Which spigot algorithm is the 3-line version using exactly? (I did some untangling of the code in limited time, but it's still pretty cryptic.)
      - tvb 5y ago
        The original pi/spigot work was done by Rabinowitz & Wagon [1]. See also the very readable works by Jeremy Gibbons [2] [3]. [1] https://en.wikipedia.org/wiki/Spigot_algorithm https://en.wikipedia.org/wiki/Spigot_algorithm [2] https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/s... [3] https://seminar-materials.iijlab.net/iijlab-seminar/iijlab-seminar-20170327.pdf https://seminar-materials.iijlab.net/iijlab-seminar/iijlab-s...