MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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


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.