News for hackers. Stuff that matters.
Re:A formula for the n’th digit of πœ‹ and πœ‹^n by sega_sai on Sunday January 15, 2023 @01:20PM (#34391607)
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).

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...

[2] https://en.wikipedia.org/wiki/Chudnovsky_algorithm

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.

https://en.wikipedia.org/wiki/Chaitin%27s_constant

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