Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The spigot algorithm for BPP formula gives hexadecimal digits of $\pi$ one at a time.

Is it possible to prove directly that this algorithm cannot be computed with bounded-memory? (From R J Lipton It seems to take $O(\log(n))$ space as an upper bound, we need a lower bound).

That would immediately imply that it wasn't periodic and hence $\pi$ is irrational.


Can this proof be done? Or maybe it depends on something difficult number theoretic result about modular exponentiation? but if it could be reduced to something like that, that would be interesting too.

share|improve this question
    
If we can prove that a particular algorithm is "lousy," that doesn't show there can't be a good one. –  André Nicolas Feb 5 '13 at 17:18
    
@Amzoti, why did you delete my note about O(log(n))? –  user58512 Feb 5 '13 at 17:23
    
Your comment got cut off. Can it be posted again? –  André Nicolas Feb 5 '13 at 17:32
1  
@user58512: sorry, it was accidental and not intentional. Regards –  Amzoti Feb 5 '13 at 17:52
1  
A bit tangential but if you do not already know it this is a delightful example of a decimal spigot algorithm for $\pi$. (I'd call BBP a digit extraction algorithm instead.) –  WimC Feb 5 '13 at 20:42

Your Answer

 
discard

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