Re:A Million Digits of Pi in 9 Lines of JavaScript
by dmurray on Thursday September 12, 2019 @03:41PM
(#20955552)
> 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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by simonbw on Thursday September 12, 2019 @07:20PM
(#20957539)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by soulofmischief on Friday September 13, 2019 @02:01AM
(#20959574)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by ajennings on Thursday September 12, 2019 @08:30PM
(#20957925)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by zamadatix on Friday September 13, 2019 @08:14AM
(#20961367)
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).
Re:A Million Digits of Pi in 9 Lines of JavaScript
by ajennings on Friday September 13, 2019 @11:58AM
(#20963259)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by zamadatix on Thursday September 12, 2019 @08:17PM
(#20957852)
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
Re:A Million Digits of Pi in 9 Lines of JavaScript
by jrochkind1 on Friday September 13, 2019 @09:06AM
(#20961716)
> 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?
Re:A Million Digits of Pi in 9 Lines of JavaScript
by zamadatix on Friday September 13, 2019 @08:18PM
(#20967989)
> 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.
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).
Re:A Million Digits of Pi in 9 Lines of JavaScript
by ehsankia on Thursday September 12, 2019 @10:16PM
(#20958540)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by Porygon on Thursday September 12, 2019 @03:30PM
(#20955415)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by wasnthere on Thursday September 12, 2019 @03:50PM
(#20955646)
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)
Re:A Million Digits of Pi in 9 Lines of JavaScript
by recursive on Friday September 13, 2019 @06:37PM
(#20967357)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by Thorrez on Thursday September 12, 2019 @10:14PM
(#20958524)
Will adding developer-centric features help reduce vulnerabilities? Generally adding any feature would increase vulnerabilities because of the increased surface area.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by AdmiralAsshat on Thursday September 12, 2019 @04:29PM
(#20956092)
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!
Re:A Million Digits of Pi in 9 Lines of JavaScript
by joeyrideout on Thursday September 12, 2019 @04:50PM
(#20956306)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by mef51 on Thursday September 12, 2019 @04:49PM
(#20956289)
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
Re:A Million Digits of Pi in 9 Lines of JavaScript
by bakul on Friday September 13, 2019 @04:20AM
(#20960201)
> 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).
Re:A Million Digits of Pi in 9 Lines of JavaScript
by 52-6F-62 on Sunday September 15, 2019 @12:48PM
(#20978112)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by ajennings on Thursday September 12, 2019 @05:07PM
(#20956465)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by mjcohen on Thursday September 12, 2019 @03:58PM
(#20955741)
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).
Re:A Million Digits of Pi in 9 Lines of JavaScript
by russellbeattie on Thursday September 12, 2019 @10:43PM
(#20958697)
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!
Re:A Million Digits of Pi in 9 Lines of JavaScript
by at-fates-hands on Thursday September 12, 2019 @05:36PM
(#20956724)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by ajennings on Thursday September 12, 2019 @05:14PM
(#20956532)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by minitech on Friday September 13, 2019 @02:44AM
(#20959782)
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…)
Re:A Million Digits of Pi in 9 Lines of JavaScript
by ajennings on Friday September 13, 2019 @10:48AM
(#20962649)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by ajennings on Thursday September 12, 2019 @03:03PM
(#20955112)
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.
Re:A Million Digits of Pi in 9 Lines of JavaScript
by hsnewman on Thursday September 12, 2019 @03:04PM
(#20955123)
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));
Re:A Million Digits of Pi in 9 Lines of JavaScript
by reificator on Monday September 23, 2019 @05:01PM
(#21053605)
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)
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.
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?
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.
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.
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
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 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).
Does anyone on the Spidermonkey team have some insight?
The open issues this bug depends on is a pretty good list of bigint-related performance enhancements that haven't been implemented yet.
I'm OK with that.
But some users want to do it.
I don't think BigInt is some adtech anti-feature.
edit: There also some nice formulae for quick convergence in this article: https://julialang.org/blog/2017/03/piday
EDIT: I understand now, the numerator on the first term is ascending odds and the denominator is ascending evens. Thanks for everyone's help!
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.
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.
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
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.)
equivalently you just list odds on the numerator and evens in the denominator
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).
http://archive.is/hUo6Q
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.
Anyway I wouldn’t worry too much. It’s likely just stodgy corporate environments that put those kinds of controls in place.
bc -l <<< "scale=$n; 4*a(1)"
Learned three new things making a dumb HN joke... not bad!
http://numbers.computation.free.fr/Constants/TinyPrograms/ti...
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.
map$l+=(-1)$_/(1-$_2)4,1..<>;die$l
[0]: https://tio.run/##K0gtyjH9/z83sUAlR9tWQ9dQUyVeX8NQVyXeSNNEx1...
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.
Edit: added a simpler series from https://math.stackexchange.com/a/14116:
[1] https://imgur.com/a/YtA8kUx[2] https://en.wikipedia.org/wiki/Double_factorial
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.
Got you beat, js.