3
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – bobuhito
    May 26, 2013 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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