3 ms·
To those who might have missed what the parent is talking about, in 1995 a formula was discovered that lets you calculate the n'th bit of pi without calculating
by randomwalker 18y ago
To those who might have missed what the parent is talking about, in 1995 a formula was discovered that lets you calculate the n'th bit of pi without calculating the previous n-1 bits. This surprised everyone.
The consequence is that you can compute the n'th bit in essentially linear time, and essentially constant memory. By traditional methods, computing the quintillionth bit would be unthinkable.
However, I doesn't look like the algorithm is parallelizable in a meaningful way. Any thoughts?
http://en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula http://en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula
- cperciva 18y agoThe BBP algorithm is not only parallelizable, it's embarrassingly parallel. Each term in the series can be computed independently of the rest. In case you missed half of the joke: The PiHex project computed the quadrillionth bit of Pi back in 1998-2000... and was run by yours truly.
- randomwalker 18y agoI sure did. Funny thing is, I was into this stuff back then (at one point me and another guy were chasing the record for the largest 7-tuple in arithmetic progression; we ended up with the second largest), so I'm sure I heard about your effort at the time. BBP survives in my memory a decade later, but not PiHex. I have to say though, your original comment was definitely an obscure reference, even on HN :-)
- cperciva 18y agoI have to say though, your original comment was definitely an obscure reference, even on HN I think a lot of people who have been here for longer than you were aware of my connection to PiHex -- it has come up a few times.
- icey 18y agoNot all of us keep our leather bound "Life and Times of Colin Percival" on our desks. Some of us keep them under our pillows so we can have sweet, sweet cperciva dreams.
- randomwalker 18y agoJust read that comment again, I meant the largest 7-tuple of primes in arithmetic progression. Otherwise that doesn't make any sense :-)