Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There is one, how do you think we compute digits of pi.


So here's a bet:

I give you the 10^100th digit of the above algorithm and you give me the 10^100th digit of pi.

Whoever fails owes the other side 10 BTC.


There is an algorithm to get the nth digit of pi. It's just that it does not run in constant time


I kind of addressed this here: https://news.ycombinator.com/item?id=31966228


If your argument is "These algorithms have differing degrees of computational complexity" then that doesn't actually demonstrate that one can't be algorithmically determined


What I meant is:

Describe the n-th digit of an irrational number without calculating all previous positions of the number.

If pi were a sequence of digits, there is no algorithm to calculate it other than by calculating pi but there is one for op's number. The very fact that he could show the algorithm for creating the sequence of numbers in his post is indicative of that.

For pi such an algorithm doesn't exist (other than calculating pi itself).

I wanted to emphasize this by talking about the "sequence of digits" in my original reply but apparently I failed at explaining this well.


Various algorithms to compute the n-th digit of pi exist, eg https://bellard.org/pi/pi_n2/pi_n2.html.


I can't really tell to what extent you're not computing previous digits (or doing work that could quickly be used to come up with these previous digits) with this algorithm but O(n^2) seems quite heavy compared to O(1) (I expect) to get the n'th digit of op's number.

Maybe I should rephrase it:

My assumption is: If there is an O(1) algorithm to determine the n-th digit of an irrational number x then the number is still "of a different class" than the likes of pi and there OP might not be able to induce things from this "lesser class of irrational numbers"

However, it's just an intuition


How could it possibly be O(1)? That doesn't even give you time to read every bit of the input number.


Why, how is that related to the existence of an algorithm?


I narrowed down "algorithm" to a specific sort of algorithm in the original reply.


Ok! I'll let you know when I'm finished calculating - hope you're still alive by then




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: