A Million Digits of Pi in 9 Lines of JavaScript
ajennings.net> 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.
I wonder if base 4 math is how people recite this out loud.
His 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?
Any numeric representation bigger than your CPU register will not have a fixed operation cost.
It's not just the comparisons, it's the additions, multiplications and divisions too. When you enter 10,000, each iteration of the loop is working with numbers 10,000 digits long. When you enter 100,000, each iteration is working with numbers 100,000 digits long, which I imagine makes every operation slower.
A number fills the same space in your registers regardless of size, up until the max size, at which point it must be split into multiple operations, and that's when it takes longer.
The script uses BigInts to implement (sort of) fixed point arithmetic. So with 100k as input, each operation works at a much higher precision.
I'd bet a good portion of the difference is between rendering the additional digits as it goes.
I didn't note timing numbers, but rendering digits in hex was basically instantaneous, even when doing a million (decimal) digits.
Rendering the digits in decimal was significant delay (like 40 seconds for a million digits). That's why it just shows the hex until the very end, and it shows how long the decimal conversion takes.
You sure you don't mean converting digits to hex instead of rendering? The constant rendering of the hex digits as the work progresses results in a ~3x slowdown for 100k digits in my testing (see my other comment in this tree).
Maybe you're right. I know displaying in hex was way faster than displaying in decimal and seemed fast enough, so I stopped there. I didn't test rendering speed specifically.
Doing a million digits in the console (with no status updates) took about an hour and doing it in that page took just over two hours.
What do you mean, doesn't it do that either way?
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.
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
> 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?
> I may be confused. But you have looked at the demo, right?
I have run the demo multiple times, how else would I have generated the time it took for me to run it in the comment above :).
> 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".
"Digits done" is the number of correct digits, not the number of displayed digits. It's possible your screen area is too small to notice the difference.
Here is an in progress shot of 10k at 2088 "Digits done" https://i.imgur.com/Fbuw2sc.png
Here is an in progress shot of 100k at 1849 "Digits done" https://i.imgur.com/O1gTogQ.png
As you can see "Digits done" ~= "Digits displayed" in this demo by any means. It simply represents the number of digits that will no longer change as the calculation continues, it is still displaying all the digits every update regardless if they are "done" or not which is where the inefficiencies in rendering come in (and based on the above benchmarks outweigh any other inefficiencies with number size substantially).
Aha, I see, thanks!
Wow, 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?
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.
Looks 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.
It 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.
What 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.
Alternatively, you can generate Pi digits one by one in a streaming way: https://observablehq.com/@mourner/calculating-pi-digits
JS Error `No identifiers allowed directly after numeric literal` when running http://ajennings.net/pi.html on Mac OS Mojave 10.14.6, Safari 12.1.2 (14607.3.9)
Safari does not support BigInt yet it seems.
Safari seems to be consistently behind these days, not sure why.
Apple seems to be the only browser developer that makes user-centric changes first, not developer-centric.
I'm OK with that.
It seems user-centric to you know... make the browser work for what users what to use it for. Like generating digits of pi.
Yes I'm sure there's a lot of consumers that want to calculate large amounts of digits of Pi in their browser..
I didn't say that. You're moving goalposts anyway. Calculating pi isn't the only use for big ints. The more practical application is maybe crypto or something.
But some users want to do it.
Given their $$$ seems like they could do both.
I don't think BigInt is some adtech anti-feature.
Safari also does releases less often than Chrome/Firefox. They are behind, but not by that much.
Given the recent influx of iOS exploits that have centered around WebKit they should probably adjust that priority
Will adding developer-centric features help reduce vulnerabilities? Generally adding any feature would increase vulnerabilities because of the increased surface area.
They are afraid the browser is going to kill their cash cow.
Meh Safari is the new IE...
Also broken on Mobile Safari / iOS 12.4.1
A 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-c...
edit: There also some nice formulae for quick convergence in this article: https://julialang.org/blog/2017/03/piday
Can 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!
If you look at the Taylor series link, you can see the sum representations of trigonometric functions.
So for instance, the 3/5/7 is just the (2n+1) value.
The other looks like the sum of the product of (2n-1)/(2n) for values 1 to n.
Remove 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.
4th step is 1357/2468
Is that simplified? I'm just going off of this image: http://ajennings.net/blog/images/formula.png
me 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
Aha, yes, I edited my post now to say 4th line not 4th step. Leave it to HN to get an off-by-one error :)
odds, not primes.
And I'm sorry if it looks like 13 over 24. It's supposed to look like 1/2 times 3/4. (The next term adds 5/6, and so on.)
odds 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
> 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).
For those of us behind work proxies that dumbly think this site is "domain parking" or worse:
Personal 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.
Not 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.
archive.is blocks resolution from the cloudflare recursive resolver. please consider using web.archive.org which doesn't block anyone.
Good to know, thanks
On 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)"
Yes, 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.
The 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).
I think this section on Wikipedia is relevant: https://en.wikipedia.org/wiki/Approximations_of_%CF%80#Grego...
I 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!
I 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/ti...
This also takes a lot of RAM. Keep an eye on it during longer executions or the swapping could make your box pretty unusable.
I 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.
It 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.
Not sure what it is exactly, but forcing a garbage collection (using the "minimize memory usage" button in about:memory) doesn't make any difference.
I still can't work out how the formula shown translates to the code given. Any hints?
I'm interested to see how the computation time would progress with the recent V8 memory enhancements.
let 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));
That 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…)
this 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
Doesn't work for me [0]. Perhaps HN messed it up somehow?
[0]: https://tio.run/##K0gtyjH9/z83sUAlR9tWQ9dQUyVeX8NQVyXeSNNEx1...
To post code, indent it with two spaces, or HN will turn asterisks into italics on/off.
It will be much faster if you don't update the HEX values all the time (they are not that interesting anyway).
Displaying 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.
What is the actual equation? They just list the first couple of terms.
Continuing the pattern it's
n!! is double factorial, the product of odd or even numbers up to n (depending on whether n is odd or even) [2].$\pi = 3 + \sum_{k=1}^\infty 3 \frac{(2k-1)!!}{(2k)!!} \frac{1}{2k+1} \frac{1}{4^k}$ [1].Edit: added a simpler series from https://math.stackexchange.com/a/14116:
[1] https://imgur.com/a/YtA8kUx$\pi = \sum_{k=0}^{\infty} \frac{(2k)!!}{(2k+1)!!} \left(\frac{1}{2}\right)^{k-1}$Good 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.
The 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));
Is there a BigDecimal, Money, or similar coming to JS?
You could probably emulate them. For example, Money would just be BigInt/100.
infinite series ..an amazing discovery
wget "https://www.piday.org/million/"
Got you beat, js.
Until 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)