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

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

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|cite|improve this answer
@Gerry, Thanks for the reference. – Victor Miller Jul 6 '11 at 13:57
A link to the paper: – Kaveh Jul 15 '11 at 16:10

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.