3 ms·
It is all curious, but it seems that procedure that calculates the n-th digit using some other functions that require O(n) calculations (i.e. Bernoulli numbers
by sega_sai 4y ago
It is all curious, but it seems that procedure that calculates the n-th digit using some other functions that require O(n) calculations (i.e. Bernoulli numbers) is not that exciting, as it's just a speedup comparing to a naive calculation (maybe a big one but still).
Although because pi is a transcendental number maybe it is impossible to have an algorithm to return the n-th digit in O(1) operations? Does anyone know ?
Upd: thinking more about it, just to read all the digits of number n, one needs log(n) operations, so I guess anything that has performance of O(log(n)) can be considered easy (i.e. the digits of rational numbers can be computed in O(logn).
- tooltower 4y agoThe normal method for computing digits of pi is not O(n), so this could still be interesting. I think it's probably better to compare this with the BBP formula [1]. The commonly used algorithm for pi I think still takes O(n log^3 n) time [2] [1] https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%9... [2] https://en.wikipedia.org/wiki/Chudnovsky_algorithm https://en.wikipedia.org/wiki/Chudnovsky_algorithm
- kdkdk 4y agoEven rational numbers which have repeating digits at the end are not O(1) because in order to calculate the n-th digit you need to calculate n modulo k where k is the length until the number repeats its digits, which needs to read the entire input number n (thus runs in O(log(n)). The only exception are rational numbers with k being a power of two. Take 0.1010101010…, you can get the n-th digit by reading off the smallest digit of n and checking whether it is a 0 or a 1. There are transcendental numbers where the n-th digit can be computed in O(log n) like Champerowne constant though.
- ur-whale 4y agoThe 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.
- paulpauper 4y agoexactly. this paper is trivial, sorry to say.