Fast exponentiation when only first k digits are r

问题:

This is actually for a programming contest, but I've tried really hard and haven't got even the faintest clue how to do this.

Find the first and last k digits of n^m where n and m can be very large ~ 10^9.

For the last k digits I implemented modular exponentiation.

For the first k I thought of using the binomial theorem upto certain powers but that involves quite a lot of computation for factorials and I'm not sure how to find an optimal point at which n^m can be expanded as (x+y)^m.

So is there any known method to find the first k digits without performing the entire calculation?

Update 1 <= k <= 9 and k will always be <= digits in n^m

回答1:

not sure, but the identity n^m = exp10(m log10(n)) = exp(q (m log(n)/q)) where q = log(10) comes to mind, along with the fact that the first K digits of exp10(x) = the first K digits of exp10(frac(x)) where frac(x) = the fractional part of x = x - floor(x).

To be more explicit: the first K digits of n^m are the first K digits of its mantissa = exp(frac(m log(n)/q) * q), where q = log(10).

Or you could even go further in this accounting exercise, and use exp((frac(m log(n)/q)-0.5) * q) * sqrt(10), which also has the same mantissa (+ hence same first K digits) so that the argument of the exp() function is centered around 0 (and between +/- 0.5 log 10 = 1.151) for speedy convergence.

(Some examples: suppose you wanted the first 5 digits of 2¹⁰⁰. This equals the first 5 digits of exp((frac(100 log(2)/q)-0.5)*q)*sqrt(10) = 1.267650600228226. The actual value of 2¹⁰⁰ is 1.267650600228229e+030 according to MATLAB, I don't have a bignum library handy. For the mantissa of 2^{1,000,000,000} I get 4.612976044195602 but I don't really have a way of checking.... There's a page on Mersenne primes where someone's already done the hard work; 2^20996011-1 = 125,976,895,450... and my formula gives 1.259768950493908 calculated in MATLAB which fails after the 9th digit.)

I might use Taylor series (for exp and log, not for n^m) along with their error bounds, and keep adding terms until the error bounds drop below the first K digits. (normally I don't use Taylor series for function approximation -- their error is optimized to be most accurate around a single point, rather than over a desired interval -- but they do have the advantage that they're mathematically simple, and you can increased accuracy to arbitrary precision simply by adding additional terms)

For logarithms I'd use whatever your favorite approximation is.

回答2:

Well. We want to calculate and to get only n first digits.

Calculate by the following iterations:

You have . Calcluate each not exactly. The thing is that the relative error of is less than n times relative error of a.

You want to get final relative error less than . 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.

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)

回答3:

Suppose you truncate at each step? Not sure how accurate this would be, but, e.g., take n=11 m=some large number and you want the first 2 digits.

recursively:

1. 11 x 11 -> 121, truncate -> 12 (1 truncation or rounding) then take truncated value and raise again

2. 12 x 11 -> 132 truncate -> 13 repeat,

3. (132 truncated ) x 11 -> 143. ...

and finally add #0's equivalent to the number of truncations you've done.

回答4:

Have you taken a look at exponentiation by squaring? You might be able to modify one of the methods such that you only compute what's necessary.

In my last algorithms class we had to implement something similar to what you're doing and I vaguely remember that page being useful.