c++ - first n digits of an exponentiation

Question

How do i determine the first n digits of an exponentiation (a^b).

eg: for a = 12, b = 13 & n = 4, the first 4 digits are 1069.

Answer 1

Calculate a^b by the following iterations:

a₁ = a¹,
a₂ = a²,
...
a_i = aⁱ,
...
a_b = a^b

You have a_i+1 = a_i×a. Calcluate each a_i not exactly. The thing is that the relative error of a^b is less than n times relative error of a.
You want to get final relative error less than 10^-n. Thus relative error on each step may be . Remove last digits at each step.

For example, a=2, b=16, n=1. Final relative error is 10^-n = 0.1. Relative error on each step is 0.1/16 > 0.001. Thus 3 digits is important on each step. If n = 2, you must save 4 digits. Common rule: save [n+log₁₀ b] digits at each step.

2 (1), 4 (2), 8 (3), 16 (4), 32 (5), 64 (6), 128 (7), 256 (8), 512 (9), 1024 (10) → 102,
204 (11), 408 (12), 816 (13), 1632 (14) → 163, 326 (15), 652 (16).

Answer: 6.

This algorithm has a compexity of O(b). But it is easy to change it to get O(log b)