How to check if a^b is smaller than n

Question

given 2 positive integers a and b (1 < a,b < 10000), I want to make sure a^b < 10000.

the problem is I can't just solve a^b, given that 64^64 is long enough to break integer size.

how can I have this answer fast? I thought about using exponentiation by squaring but I didn't come up with an answer yet.

thanks

Answer 1

Take the a-base logarithm of both sides of the inequality.

For positive integers a and b, the following inequalities are equivalent:

    a^b < 10000

    log_a(a^b) < log_a(10000)

    b < log_a(10000)

The latter can be calculated without overflow issues.

Note also that with the change of base formula this can be written with a log₁₀ function:

    b·log₁₀(a) < 4