# Comparing large prime powers.

• Nov 8th 2010, 05:32 AM
markyparky
Comparing large prime powers.
I have two very large primes (a, b) , each raised to a large (non-prime) integer powers (p,q) .

I want to evaluate the comparison:

a^p >= b^q

However, I don't want to attempt to calculate a^p, b^q since the results will be astronomically huge, and I only need to know which is the largest.

Obviously if a>b and p>q then the answer is trivial, however in the general case I'm stumped...

Any suggestions ?
• Nov 8th 2010, 05:16 PM
roninpro
What about looking at their logarithms? It suffices to compare \$\displaystyle p\log a\$ and \$\displaystyle q\log b\$.
• Nov 8th 2010, 11:55 PM
markyparky
Thanks, but...
Thanks for the reply, however I am dealing with very large ( hundreds of digits ) numbers, and although this approach would be a lot easier to calculate, it still involves a considerable amount of computation for very large numbers...

I was looking at the following approach to break up the numerator and iteratively
approach the answer in a loop:

if a^p < b^q
then (a^p) mod D =a^p // where D = b^q
= ( (a mod D ) * (a^(p-1) mod D ) ) mod D

Then the algorithm would run something like:
In a loop of 'p' iterations keep a result 'r' (initially 1 ? ). For each iteration multiply 'r' by (a mod D ). If the result is greater than D then result = result - D.
Obviously r will always be < 2D.

The problem here is that we still need 'p' big multiplications etc, the size of the integers involved would be governed by the size of D.

Cheers
• Nov 9th 2010, 06:57 AM
roninpro
Wikipedia says that a logarithm can be computed in \$\displaystyle O(\log n \ M(n))\$ time, where \$\displaystyle M(n)\$ is the speed of your multiplication. That does not seem slow at all.

Did you actually try the logarithm approach for whatever numbers you are working with?

Regarding your proposal, working modulo \$\displaystyle b^q\$ actually doesn't help. You still have to compute \$\displaystyle b^q\$, and in the worst case scenario, all of your multiplications of \$\displaystyle a\$ will be run as integers. So in other words, your method is just a complicated way of using brute force.
• Nov 9th 2010, 07:07 AM
markyparky
Thanks, I'm definately going to look into it at the weekend
Thanks for the reply, I'm definately going to look into the log approach at the weekend when I've got some time to sit down and look at it analytically.

I'm thinking that I may be able to evaluate either side as a series, taking the difference of the series and see if it converges to a positive or negative to indicate which side of the inequality is greater.

Thanks for pointing me in this direction. I'll post again here when I've got a bit further in a few days time. I'm a programmer, not a mathematician, so there's a good chance that I'll miss the obvious solution if I don't know the maths!

Cheers.
• Nov 9th 2010, 07:08 AM
roninpro
Sounds good. Best of luck!