Results 1 to 6 of 6

Math Help - Comparing large prime powers.

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    6

    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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    What about looking at their logarithms? It suffices to compare p\log a and q\log b.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    6

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Wikipedia says that a logarithm can be computed in O(\log n \ M(n)) time, where 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 b^q actually doesn't help. You still have to compute b^q, and in the worst case scenario, all of your multiplications of a will be run as integers. So in other words, your method is just a complicated way of using brute force.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    6

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Sounds good. Best of luck!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime factoring a large number.
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 10th 2011, 04:10 AM
  2. Prove a large number is prime
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 1st 2011, 10:17 PM
  3. Finding derivative involving large powers.
    Posted in the Calculus Forum
    Replies: 7
    Last Post: January 15th 2010, 07:16 PM
  4. Another question about large powers of matrices
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 19th 2009, 05:43 PM
  5. Generating Large Prime Numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: July 26th 2009, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum