Algorithm for ProjectEuler Problem 99

Question

From http://projecteuler.net/index.php?section=problems&id=99

Comparing two numbers written in index form like 2¹¹ and 3⁷ is not difficult, as any calculator would confirm that 2¹¹ = 2048 3⁷ = 2187.

However, confirming that 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

How might I approach this?

Answer 1

Not a full solution, but some ideas. You can use the following formula:

log(a^x) = x*loga

The log10 can easily be estimated as number of digits. The log2 can easily be estimated by counting right shifts.

Based on the above you could narrow the list significantly. For the remaining numbers, you would have to do full calculations. Are math functions allowed in project Euler? If yes, it would be better to use logarithms.

Answer 2

One possible approach would be to use logarithm identities (that is, a^b is identical to e^{b * ln a}). As a matter of fact, a^b is identical to base^{b * log_base a} for all bases except 0 and 1.

Answer 3

Since the logarithm is a monotonic function, instead of a^x you could compare x * log a to find the maximum. You might need to take numerical precision into account, though.

Answer 4

Comparing exponent * log(base) instead of base^exponent for each line in the file works for this problem without taking precision into account. This is certainly the best solution from a mathematical perspective, but I just wanted to point out that this isn't really necessary.

Another possible solution is to divide every number in the file by some constant (say 100,000) before performing the exponentiation on the now smaller numbers. Since you're comparing all of the values to each other, scaling them all down by a constant factor doesn't affect the final outcome.