4 ms·
The interesting question is: are there real numbers whose N-th digit provably cant be calculated in O(N)?
by ur-whale 4y ago
The interesting question is: are there real numbers whose N-th digit provably cant be calculated in O(N)?
- yongjik 4y agoEven better: there are (well defined) real numbers whose N-th digit provably cannot be computed at all. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
- cmeacham98 4y agoI don't know of any with practical use, but you can fairly easily define a contrived one: cmeacham98's constant: a number where the `n`th digit is the `2^n`th digit of pi
- ur-whale 4y agoYou're assuming that the N-th digit of pi can't be computed in sub-linear time, no?
- cmeacham98 4y agoYes, I didn't bother trying to look up if that's 100% proven. If it's not you can just substitute pi for any number where it is provable.