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

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.