Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for speed).

Can any of the common irrational constants be currently computed with the same low memory, but in faster time? Please consider constants which combine integers and $\pi$, natural exponential functions, and/or root functions (e.g., $\pi$, $\pi^2$, $e$, $e^{-\pi}$, $\sqrt2$, $\sqrt{2\pi}$).

For any such constant, I am also curious about the randomness in its binary tail. These digit extraction constraints cause correlations in the constant's tail bits which probably go to zero for high $n$ (but, for $\pi$, the Bellard/BBP constraints are too subtle for me to conclude anything). If anyone has a low-memory method to distinguish a tail of some common irrational number from random bits (with the same speed in the limit of high $n$), please comment.

share|improve this question

1 Answer 1

Liouville's constant in base 2. O(1) space (assuming streaming input) and O(log n) time (just check whether n is a power of 2, i.e. ends with all zeros).

share|improve this answer
    
For those that upvoted this, it's clearly ruled out in my question (I know it makes my question a little artificial, but this Liousville construction is even more artificial). –  bobuhito May 26 '13 at 14:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.