Re:A formula for the nβth digit of π and π^n
by tooltower on Sunday January 15, 2023 @01:37PM
(#34391766)
The 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%9...
Re:A formula for the nβth digit of π and π^n
by kdkdk on Sunday January 15, 2023 @01:45PM
(#34391852)
Even 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.
Re:A formula for the nβth digit of π and π^n
by ur-whale on Sunday January 15, 2023 @05:01PM
(#34394020)
The interesting question is: are there real numbers whose N-th digit provably cant be calculated in O(N)?
Re:A formula for the nβth digit of π and π^n
by yongjik on Sunday January 15, 2023 @05:13PM
(#34394155)
Even better: there are (well defined) real numbers whose N-th digit provably cannot be computed at all.
Re:A formula for the nβth digit of π and π^n
by cmeacham98 on Sunday January 15, 2023 @07:18PM
(#34395181)
I 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
Re:A formula for the nβth digit of π and π^n
by ur-whale on Monday January 16, 2023 @06:44PM
(#34407128)
You're assuming that the N-th digit of pi can't be computed in sub-linear time, no?
Re:A formula for the nβth digit of π and π^n
by cmeacham98 on Tuesday January 17, 2023 @10:08AM
(#34413282)
Yes, 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.
Re:A formula for the nβth digit of π and π^n
by paulpauper on Sunday January 15, 2023 @05:36PM
(#34394371)
exactly. this paper is useless, sorry to say
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).