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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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..." $\endgroup$– Federico PoloniJul 6, 2011 at 9:19
-
$\begingroup$ @Federico, good point. I added "fractional" before bit. $\endgroup$– Victor MillerJul 6, 2011 at 13:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ A link to the paper: math.tau.ac.il/~rabinoa/pub/power-algebraic.pdf $\endgroup$– KavehJul 15, 2011 at 16:10