views:

977

answers:

4

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 nm 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 nm

+1  A: 

not sure, but the identity nm = 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 nm 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 2100. This equals the first 5 digits of exp((frac(100 log(2)/q)-0.5)q)sqrt(10) = 1.267650600228226. The actual value of 2100 is 1.267650600228229e+030 according to MATLAB, I don't have a bignum library handy. For the mantissa of 21,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; 220996011-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 nm) 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.

Jason S
@nlucaroni: thanks but it's more courteous to submit thoughts like this as your own comment.
Jason S
Taylor series would not be very simple for this function. f(x) = x^n, f'(x) = nx^(n-1), f''(x) = n(n-1)x^(n-2) - you see the issue. Every term requires evaluating a function similar to the one you're trying to approximate. And if n=10^9, you need that many terms to get to the nth derivative of f
duffymo
I didn't mean Taylor series for n^m, I meant for exp() and log()
Jason S
(Will edit my response accordingly.)
Jason S
Still not the way to go, IMO. They won't converge fast enough. I'd prefer looking at Abramowitz and Stegun or something like this: http://myweb.lmu.edu/dmsmith/MComp89.pdf
duffymo
maybe i'm missing something.. what do you need K for? exp(K (m log(n)/K)) === exp(m log(n))
Kip
Because the digits come from base 10 exponentiation/logarithms, but the Taylor series is more easily expressed in terms of natural log/exp. I'll clarify.
Jason S
@Kip: Argh -- sorry, I used K in 2 places for 2 different things. I changed the log10 constant to "q" instead of "K".
Jason S
@duffymo: You have a point for log(x). For the exponential, though, its argument with my idea is going to be less than log 10 = 2.30... a faster algorithm would certainly work. I was just thinking Taylor series allow you to increase accuracy at run-time efficiently.
Jason S
A: 

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.

Steve B.
This method would need to be combined with an efficient method of exponentiation. If you want the last 10 digits of 7^23421613, you certainly don't want to perform your multiply and truncate method 23421613 times.
Juliet
this doesn't work, eg. 65^5 = 116... for k = 3but by truncation the answer is 115.
Nikhil
plus you have to watch your error bounds. even if you want only 2 digits, you need more than 2 digits in intermediate calculations.
Jason S
A: 

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.

Ben S
A: 

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

Calculate alt text by the following iterations:

alt text

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

You want to get final relative error less than alt text. Thus relative error on each step may be alt text. 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)

Alexey Malistov