8 ms·
A Million Digits of Pi in 9 Lines of JavaScript
- adossi 7y agoI'm interested to see how the computation time would progress with the recent V8 memory enhancements.
- tombert 7y agoWow, I wonder why Firefox is so much slower? Quantum seems pretty zippy overall, but maybe that's largely due to fast rendering speeds? Does anyone on the Spidermonkey team have some insight?
- war1025 7y agoLooks like they are using big integers, which I'd guess isn't something that comes up a lot, so probably hasn't been optimized for too much.
- ehsankia 7y agoIt is pretty new, and as you mention not many websites use them yet, so I'm sure there are more important optimizations the Firefox team is focusing on for now.
- opencl 7y agohttps://bugzilla.mozilla.org/show_bug.cgi?id=1366287 https://bugzilla.mozilla.org/show_bug.cgi?id=1366287 The open issues this bug depends on is a pretty good list of bigint-related performance enhancements that haven't been implemented yet.
- Porygon 7y agoWhat is benchmarked here is basically the performance of the division operation on big integers and does not represent the general performance of a browser for everyday tasks.
- hervature 7y agoWhat is the actual equation? They just list the first couple of terms.
- hsnewman 7y agoThe article says: let i = 1n; let x = 3n * (10n 1000020n); let pi = x; while (x > 0) { x = x * i / ((i + 1n) * 4n); pi += x / (i + 2n); i += 2n; } console.log(pi / (10n 20n));
- ajennings 7y agoGood question. I just presented it here the way it was given to me, as a couple initial terms and some rules on how it evolves, because I find that to be the easiest way to remember it. The actual formula looks much less friendly (because it's tricky to write "the product of the first n odd integers"), but it's a good exercise for those who are inclined.
- mkl 7y agoContinuing the pattern it's $\pi = 3 + \sum_{k=1}^\infty 3 \frac{(2k-1)!!}{(2k)!!} \frac{1}{2k+1} \frac{1}{4^k}$ [1]. n!! is double factorial, the product of odd or even numbers up to n (depending on whether n is odd or even) [2]. Edit: added a simpler series from https://math.stackexchange.com/a/14116 https://math.stackexchange.com/a/14116: $\pi = \sum_{k=0}^{\infty} \frac{(2k)!!}{(2k+1)!!} \left(\frac{1}{2}\right)^{k-1}$ [1] https://imgur.com/a/YtA8kUx https://imgur.com/a/YtA8kUx [2] https://en.wikipedia.org/wiki/Double_factorial https://en.wikipedia.org/wiki/Double_factorial
- dlojudice 7y agoIs there a BigDecimal, Money, or similar coming to JS?
- mark-r 7y agoYou could probably emulate them. For example, Money would just be BigInt/100.
- 52-6F-62 7y agoFor those of us behind work proxies that dumbly think this site is "domain parking" or worse: http://archive.is/hUo6Q http://archive.is/hUo6Q
- ajennings 7y agoPersonal domain. I haven't used it for much over the years. The hosting is static pages on S3. I wonder if there's anything I could do to avoid the domain getting flagged. Maybe it's because the root page on the domain is just a quote.
- 52-6F-62 7y agoNot sure. Where the company I work for operates they have some very weird proxy setup (not my company’s rule but the host). Largely it seems only effective at blocking legitimate content for nonsense reasons. My own site gets blocked on occasion, though I’ve lazily let the cert expire. That reminds me.... Anyway I wouldn’t worry too much. It’s likely just stodgy corporate environments that put those kinds of controls in place.
- snek 7y agoarchive.is blocks resolution from the cloudflare recursive resolver. please consider using web.archive.org which doesn't block anyone.
- 52-6F-62 7y agoGood to know, thanks
- phonebucket 7y agoA fun related thread on math stackexchange which has several examples of series which converge quickly to pi: https://math.stackexchange.com/questions/14113/series-that-converge-to-pi-quickly https://math.stackexchange.com/questions/14113/series-that-c... edit: There also some nice formulae for quick convergence in this article: https://julialang.org/blog/2017/03/piday https://julialang.org/blog/2017/03/piday
- dmurray 7y ago> this simple one still converges at about 0.6 decimal digits per term. Quick proof of this: as the number of terms n in the sum goes to infinity, the ratio of each term to the previous one is approximately 1/4 - the first factor contributes m/(m+1), the second q/(q+2) for some m and q that go to infinity along with n, the third contributes 1/4. If we counted base 4, then the value of each digit would be on average 1/4 of the previous one, certainly for a normal number like pi. But we count base 10, so we get log_10 4 decimal digits every time we get one base-four digit. Which is very close to 0.6.
- mycall 7y agoI wonder if base 4 math is how people recite this out loud.
- LeoPanthera 7y agoOn any standard unix system with bc installed - it's preinstalled on most of them, you can calculate pi to $n digits using bc: bc -l <<< "scale=$n; 4*a(1)"
- mjcohen 7y agoThe algorithm seems to be at least quadratic in the length. On a 2014 i7 Mac mini, (n, time(sec)) = (1000, 0.29), (2000, 1.65), (4000, 9.70), (8000, 58.42).
- notfashion 7y agoI think this section on Wikipedia is relevant: https://en.wikipedia.org/wiki/Approximations_of_%CF%80#Gregory%E2%80%93Leibniz_series https://en.wikipedia.org/wiki/Approximations_of_%CF%80#Grego...
- ajennings 7y agoYes, 4 * arctan(1) will do in any language. I just find some joy in knowing a formula that uses only addition, multiplication, and addition, and computing it directly.
- deleted 7y ago[deleted]
- wasnthere 7y agoJS Error `No identifiers allowed directly after numeric literal` when running http://ajennings.net/pi.html http://ajennings.net/pi.html on Mac OS Mojave 10.14.6, Safari 12.1.2 (14607.3.9)
- MildlySerious 7y agoSafari does not support BigInt yet it seems.
- oehtXRwMkIs 7y agoSafari seems to be consistently behind these days, not sure why.
- LeoPanthera 7y agoApple seems to be the only browser developer that makes user-centric changes first, not developer-centric. I'm OK with that.
- hnaccy 7y agoGiven their $$$ seems like they could do both. I don't think BigInt is some adtech anti-feature.
- nicoburns 7y agoSafari also does releases less often than Chrome/Firefox. They are behind, but not by that much.
- wp381640 7y agoGiven the recent influx of iOS exploits that have centered around WebKit they should probably adjust that priority
- Thorrez 7y ago
- sp332 7y agoThis also takes a lot of RAM. Keep an eye on it during longer executions or the swapping could make your box pretty unusable.
- ajennings 7y agoIt should take 415kB to store a million digit number, and the algorithm only needs to keep two of them. So, 1MB total to calculate a million digits of pi. I wonder if there are a lot of temporary allocations that build up until they get garbage collected.
- sp332 7y agoNot sure what it is exactly, but forcing a garbage collection (using the "minimize memory usage" button in about:memory) doesn't make any difference.
- at-fates-hands 7y agoI used to have a script on my personal site that would just continue to compute digits of Pi until your browser crashed. I finally took it down after too many recruiters and potential employers keep clicking on the link that said, "Don't Click This." and complaining about it. I did the same thing when I was testing it. I would keep an eye on the system RAM resources graph as the script was running. Watching the RAM start to spike was oddly satisfying. It's pretty scary to me how easy it is to crash a browser these days with something so simple.
- paulpauper 7y agoinfinite series ..an amazing discovery
- AdmiralAsshat 7y agoCan someone explain the logic behind the evolution of the fractions at each stage? I see that (1/4) becomes (1/4^2) and (1/4^3), but it's not obvious to me how (1/3)->(1/5)->(1/7) flows (odds? primes?), or (1/2) -> (13/24) -> (135/246). EDIT: I understand now, the numerator on the first term is ascending odds and the denominator is ascending evens. Thanks for everyone's help!
- mef51 7y agoodds to get the 1/3, 1/5, 1/7, 1/9, etc. term and count by alternating digits on the numerator and denominator up to the next even number to get 1/2, 13/24, 135/246, 1357/2468, etc for the first term. equivalently you just list odds on the numerator and evens in the denominator
- joeyrideout 7y agoRemove the leading 3 and the trailing term of 1/4 increasing in power. You are left with this (in the 4th line): 1 3 5 1 - - - - 2 4 6 7 The pattern I see is that, starting from the top left and reading numerator, denominator, numerator, denominator and so on gives: 1 2 3 4 5 6 7 if you ignore the last numerator. I may have it wrong, but that looks like the pattern.
- mef51 7y ago4th step is 1357/2468
- joeyrideout 7y agoIs that simplified? I'm just going off of this image: http://ajennings.net/blog/images/formula.png http://ajennings.net/blog/images/formula.png
- mef51 7y agome too, the pattern to me is odds on the numerator and evens in the denominator, and the second fraction goes 1/3, 1/5, 1/7, 1/9... i think we're saying the same thing i misunderstood your comment. 1357/2468 is the first fraction of the NEXT line that isnt in the image
- deleted 7y ago[deleted]
- jrochkind1 7y agoHis demo page, in my Chrome, if I enter 10000, it takes about 2 seconds to finish with 10k digits. But if I enter 100k, it takes 30 seconds to get to reporting 10k digits worth of progress. Hmm. Have to think about that one. Just cause it's asking JS to do comparisons of much larger numbers?
- zamadatix 7y agoI'd bet a good portion of the difference is between rendering the additional digits as it goes.
- jrochkind1 7y agoWhat do you mean, doesn't it do that either way?
- zamadatix 7y agoSure but one has 10x more digits than the other so takes a heck of a lot longer to convert and display the string for the same number of iterations. As a quick test of my theory the majority of the time is being spent trying to display the progress: - Default 100,000 = 58.276 - CSS display: none; = 22.359 - Display when done = 20.057
- jrochkind1 7y ago> Sure but one has 10x more digits than the other so takes a heck of a lot longer to convert and display the string for the same number of iterations. Hm, I was comparing the same number of digits displayed on screen though. One takes 2s to compute and display 10k digits of information on screen, one takes 30s to compute and display 10k digits of information on screen. same number of digits. At least according to the "progress" output that reads "Digits done". I may be confused. But you have looked at the demo, right?
- zamadatix 7y ago
- userbinator 7y agoI thought it would be the "spigot" algorithm, which is based on Bellard's formula (yes, that Bellard) and yields similarly small programs: http://numbers.computation.free.fr/Constants/TinyPrograms/tinycodes.html http://numbers.computation.free.fr/Constants/TinyPrograms/ti...
- deleted 7y ago[deleted]
- russellbeattie 7y agoI was going to make a joke about just writing Math.PI.toFixed(10 * * 6), but it turns out that Number.toFixed() only supports up to 100 places AND Math.PI stops at the 50th place. Still amusing to me. Also, BigInt numbers can't be combined with non BigInt without conversion. I haven't had cause to use them yet, so I didn't know that. Learned three new things making a dumb HN joke... not bad!
- foxes 7y agolet y=3n*(10n**1000020n); const f=(i,x,p)=>{(x>0)?f(i+2n,x*i/((i+1n)*4n),p+x/(i+2n)):p/(10n**20n)} console.log(f(1n,y/8n,y)); Not sure if I can golf it anymore
- minitech 7y agoThat version already doesn’t work… once you fix the arrow function, there’s also the issue that most engines today don’t support proper tail calls, so nothing recursive will be portable. (But if it did, you could save a lot of characters by dropping unnecessary parentheses, expanding (i+1n)×4n to 4n×i+4n, replacing the const with a comma, removing semicolons…)
- sqnguyen 7y agothis is my perl golf version of the same series. You can probably can do something similar with js: map$l+=(-1)$_/(1-$_2)4,1..<>;die$l
- NieDzejkob 7y agoDoesn't work for me [0]. Perhaps HN messed it up somehow? [0]: https://tio.run/##K0gtyjH9/z83sUAlR9tWQ9dQUyVeX8NQVyXeSNNEx1BPz8bOOiUzVSXn/38A https://tio.run/##K0gtyjH9/z83sUAlR9tWQ9dQUyVeX8NQVyXeSNNEx1...
- sqnguyen 7y agoI guess so... https://tio.run/##K0gtyjH9/z83sUAlR9tWQ9dQU0tLJV5fw1BXJV7LSFPLRMdQT8/GzjolM1UlR@H/f0MDIAAA https://tio.run/##K0gtyjH9/z83sUAlR9tWQ9dQU0tLJV5fw1BXJV7LSF...
- mkl 7y agoTo post code, indent it with two spaces, or HN will turn asterisks into italics on/off.
- dingo_bat 7y agoSurprsingly, my laptop performs half as well as the author's. His is a 2014 2.5GHz i7 and mine is a 2017 4GHz i7. So why is mine slower by a factor of 2?
- craftinator 7y agowget "https://www.piday.org/million/" https://www.piday.org/million/" Got you beat, js.
- reificator 7y agoUntil you go to examine it and realize it's infinite scrolling via JS and spend all your time trying to hack around that. (Or you just grab the URL out of the request and fetch it a few times directly)
- mourner 7y agoAlternatively, you can generate Pi digits one by one in a streaming way: https://observablehq.com/@mourner/calculating-pi-digits https://observablehq.com/@mourner/calculating-pi-digits
- bakul 7y ago> this simple one still converges at about 0.6 decimal digits per term. The Chudnovsky brothers’ algorithm computes 14.18... digits per term. Its implementation in Scheme is only about a couple dozen lines of code. It computes a million pi digits in about 17.5 seconds on raspberry pi 4 in Gambit Scheme (57 seconds on the original raspberry pi, IIRC).
- ilovepeppapig 7y agoIt will be much faster if you don't update the HEX values all the time (they are not that interesting anyway).
- ajennings 7y agoDisplaying hex is quite fast (compared to trying to display decimal), though you're right that it might add up to a noticeable amount of time in the end. I did the full million digit calculation on that sample page on the same computer and it took a little over two hours (so 2.1x slowdown) but at that point I was also adding a 5ms delay every 100 terms. It is fun to scroll down and watch the "cutoff", where digits above that are not changing and digits below that are. That's just as fun in hex as it is in decimal. But yes, maybe I should add an option to turn that off.
- andig 7y agoI still can't work out how the formula shown translates to the code given. Any hints?