@article{HirvensaloKarhumakiRabinovich:JNT:2010,
    Abstract = {We consider an algorithmic problem of computing the first, i.e., the most significant digits of 2n (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.},
    Author = {Hirvensalo, Mika and Karhum{\"a}ki, Juhani and Rabinovich, Alexander},
    File = {Computing partial information out of intractable- Powers of algebraic numbers as an example - 1-s2.0-S0022314X09002364-main.pdf},
    ISSN = {0022-314X},
    Journal = {Journal of Number Theory},
    Keywords = {Efficient computability, Linear forms of logarithms, Baker theory},
    Number = {2},
    Pages = {232--253},
    Title = {Computing partial information out of intractable: Powers of algebraic numbers as an example},
    URL = {https://www.sciencedirect.com/science/article/pii/S0022314X09002364},
    Volume = {130},
    Year = {2010},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022314X09002364},
    bdsk-url-2 = {https://doi.org/10.1016/j.jnt.2009.08.009},
    date-added = {2023-10-06 15:16:19 +0200},
    date-modified = {2023-10-17 13:50:50 +0200},
    doi = {10.1016/j.jnt.2009.08.009}
}

@article{HirvensaloKarhumakiRabinovich:JNT:2010, Abstract = {We consider an algorithmic problem of computing the first, i.e., the most significant digits of 2n (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.}, Author = {Hirvensalo, Mika and Karhum{\"a}ki, Juhani and Rabinovich, Alexander}, File = {Computing partial information out of intractable- Powers of algebraic numbers as an example - 1-s2.0-S0022314X09002364-main.pdf}, ISSN = {0022-314X}, Journal = {Journal of Number Theory}, Keywords = {Efficient computability, Linear forms of logarithms, Baker theory}, Number = {2}, Pages = {232--253}, Title = {Computing partial information out of intractable: Powers of algebraic numbers as an example}, URL = {https://www.sciencedirect.com/science/article/pii/S0022314X09002364}, Volume = {130}, Year = {2010}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022314X09002364}, bdsk-url-2 = {https://doi.org/10.1016/j.jnt.2009.08.009}, date-added = {2023-10-06 15:16:19 +0200}, date-modified = {2023-10-17 13:50:50 +0200}, doi = {10.1016/j.jnt.2009.08.009} }