Are there irrational numbers for which we know that computing its nth digit would take (at least) linear/polynomial/exponential/superexponential time (wrt to length of n and with "big enough" n)?

Ty Moore

Ty Moore

Answered question

2022-11-03

Are there irrational numbers for which we know that computing its nth digit would take (at least) linear/polynomial/exponential/superexponential time (wrt to length of n and with "big enough" n)?

Answer & Explanation

boursecasa2je

boursecasa2je

Beginner2022-11-04Added 15 answers

Sure there is. Just define an irrational number x = 0. r 1 r 2 r 3 where ri is an integer computed in linear/polynomial/exponential/superexponential time (i.e. asymptotic to O ( i ) , O ( i n ) etc).
For example, you can set r i is the number of subsets of { 1 , 2 , , i } whose members sum to a prime number. (I have no idea what the time complexity of this is but I guess with a naive algorithm it would be O ( 2 i )). Then computing n digits of x is done in exponential time. Note that even if r i > 9 then just stick r i onto the end of the decimal expansion of x.
In order to make computing n digits of x exactly exponential time, you can change the previous definition to r i is the number of subsets of {1,2,…,i} whose members sum to a prime number, mod 10. Then I'm pretty sure that as long as you're using the naive algorithm, the calculation is in exponential time.
Similar methods can be used to find irrational numbers that are calculated in any other time complexity.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?