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

On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are fixed (think of $p/q = 3/2$) and $n$ varies. There were a number of suggestions, but all of them clearly had complexity proportional to $n$. So my question is, for concreteness, let $b(n) = \lfloor 2(3/2)^n \rfloor \bmod 2$ (the leading fractional bit of $(3/2)^n$). Suppose that $n$ is specified in binary. What is the complexity (both time and space) of calculating the function $b(n)$? After thinking about it for a while I wouldn't be surprised if it's exp-space hard. Does anyone know anything about this?

share|improve this question
    
You may want to change that title: when I read the question on the home page, the first thing I thought is "what's the problem, the leading bit is always 1..." –  Federico Poloni Jul 6 '11 at 9:19
    
@Federico, good point. I added "fractional" before bit. –  Victor Miller Jul 6 '11 at 13:57
add comment

1 Answer

From the review of Mika Hirvensalo, Juhani Karhumäki, and Alexander Rabinovich, Computing partial information out of intractable: powers of algebraic numbers as an example, J. Number Theory 130 (2010), no. 2, 232–253, MR2564895 (2010j:11117), it looks like there may be something of interest there.

share|improve this answer
    
@Gerry, Thanks for the reference. –  Victor Miller Jul 6 '11 at 13:57
1  
A link to the paper: math.tau.ac.il/~rabinoa/pub/power-algebraic.pdf –  Kaveh Jul 15 '11 at 16:10
add comment

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.