[HN Gopher] Pi Formulas, Algorithms and Computations (2009)
___________________________________________________________________
Pi Formulas, Algorithms and Computations (2009)
Author : h2odragon
Score : 93 points
Date : 2022-03-14 11:38 UTC (11 hours ago)
(HTM) web link (bellard.org)
(TXT) w3m dump (bellard.org)
| h2odragon wrote:
| Apologies for the bad link.
|
| Also: https://github.com/philipl/pifs
| edf13 wrote:
| 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 p!
| They were always there!
|
| How about prior-art for Patents? Every invention is already
| written in Pi!
| jzer0cool wrote:
| In layman's term, how did one discover this series which
| generates the pi digit patterns?
| abetusk wrote:
| 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%...
|
| [1] https://en.wikipedia.org/wiki/Integer_relation_algorithm
|
| [2]
| http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental...
|
| [3] http://xahlee.info/math/Simon_Plouffe_pi_formula.html
| phkahler wrote:
| >> Lattice reduction techniques give a polynomial algorithm
| to factor polynomials with integral coefficients (does the
| polynomial factor into other polynomials with integral
| coefficients)
|
| Wait, are you saying factorization of polynomials is in P?
| That doesn't feel right since factoring integers has not been
| shown to be in P (yet).
| abetusk wrote:
| Yes, that's what I'm saying.
|
| Factoring univariate polynomials with integer coefficients
| (that is, seeing if a polynomial with integer coefficients
| has smaller degree polynomial factors with integer
| coefficients) is in P [0]. Factoring univariate polynomials
| over the integers has known to be in P since the 1980s
| (since LLL came out, which is one of the major reasons why
| LLL was developed in the first place).
|
| Integer factorization is still currently unknown to be in P
| or not in P.
|
| If you see how to use polynomial factoring to factor
| integers, please let me know.
|
| [0] https://en.wikipedia.org/wiki/Factorization_of_polynomi
| als#F...
| loa_in_ wrote:
| 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.
| paulpauper wrote:
| A simple derivation of such formulas is given here
|
| https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3919892
|
| The idea is you begin with an elementary integral that yields
| the underlying constant, such as pi, and then accelerate its
| convergence by using a polynomial.
|
| Ramanujan-like pi formulas can be derived similar to the
| Fabrice Bellard one, but with an inverse cosine instead of
| elliptic integrals. Visually, the formulas look like the
| Ramanujan pi formulas, but the derivation is elementary and it
| computes pi, not the reciprocal of pi. The Bellard and Simon
| formulas use inverse trig functions as well. I think he uses
| arctan.
| omginternets wrote:
| Long live Tau, long live Tau!
|
| https://treelight.com/essays/ideas/the-way-of-the-tau-better...
| nh23423fefe wrote:
| This is like a weaker version of master to main.
| tvb wrote:
| 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
| jeffwass wrote:
| brilliant method of embedding his name in the code without
| wasting lines for comments
| divbzero wrote:
| "...signed by Dik T Winter"
| tvb wrote:
| 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.
| umvi wrote:
| FYI for those unaware - Bellard (the author of the article) is
| also the author of ffmpeg and qemu.
| paulpauper wrote:
| this guy is the epitome of computer science (along with Knuth)
| isaacimagine wrote:
| 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).
| edf13 wrote:
| Bad SSL cert on the www.
|
| Work on: https://bellard.org/pi/
| blueflow wrote:
| If the mods could fix the link? Maybe a @dang does summon them.
| enriquto wrote:
| This may be some sort of elaborate trolling on his part.
| [deleted]
| tlb wrote:
| Fixed, thanks
| amelius wrote:
| What is the fastest algorithm to find a given substring in the
| digits of Pi?
| dolmen wrote:
| 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.
| loa_in_ wrote:
| Brute force
|
| E: if you want to have reliable, consistent results that is
| Someone wrote:
| 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) or
| https://en.wikipedia.org/wiki/Leibniz_formula_for_p, 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_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 p is normal, they would, but we don't know
| whether it is)
___________________________________________________________________
(page generated 2022-03-14 23:01 UTC)