Computing partial information out of intractable: Powers of algebraic numbers as an example

We consider an algorithmic problem of computing the first, i.e., the most significant digits of n² (in base 3) and of the nth Fibonacci number. While the decidability is trivial, efficient algorithms for those problems are not immediate. We show, based on Baker's inapproximability results of transcendental numbers that both of the above problems can be solved in polynomial time with respect to the length of n. We point out that our approach works also for much more general expressions of algebraic numbers.