Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 9 of 9

Thread: Need a more efficient algorithm for finding the highest pth of a number.

  1. #1
    Junior Member
    Join Date
    Sep 2012
    Posts
    3
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Need a more efficient algorithm for finding the highest pth of a number.

    This is my algorithm so far:
        public static int getPth(int x) {
            int largestP = 1;
     
            for (int p = 1; p < x; p++) {
                for (int b = 1; b < x; b++) {
                	double ans = Math.pow(b, p);
                    if (ans > x) {
                        break;
                    }else if(ans == x) {
                    	largestP = p;
                    }
               }           
            }
     
            return largestP;	
        }
    It prints out the highest pth for 17, 625, 1024 and 10000, which is 1, 4, 10, and 4, instantly but i'm trying to speed it up finding it for 1073741824. I know the math.pow() is slow and I was wondering if anyone had any ideas on how to generally speed up the algorithm.
    Last edited by firstTimeJava; October 1st, 2012 at 09:51 AM.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    What does it mean to get the highest pth of a number?

  3. #3
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,104
    Thanks
    52
    Thanked 2,285 Times in 2,256 Posts

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    Save the results of the previous computation and multiply it by the number.
    x^2 = x*x
    X^3 = x^2 * x
    x^4 = x^3 * x
    If you don't understand my answer, don't ignore it, ask a question.

  4. #4
    Junior Member
    Join Date
    Sep 2012
    Posts
    3
    My Mood
    Confused
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    Yea that's how I figured to get around the math.pow() I was just having some trouble implementing that into the algorithm.

  5. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    From what I can tell, you want to calculate the largest positive integer value of p < x such that pow(b,p) == x, for b=1..x. Correct?

    I haven't benchmarked these at all, but given a certain p and x it is possible to calculate directly the value of b.

    b = pow(x, 1 / p)

    It's also possible to calculate p directly given b and x:

    p = log(x) / log(b)

    I'm inclined to believe that one or both of these operations are faster than using a second loop to calculate b and p, though that's for you to try out.

    edit: fixed mathematical error
    Last edited by helloworld922; October 2nd, 2012 at 02:02 AM.

  6. #6
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    Quote Originally Posted by firstTimeJava View Post
            for (int p = 1; p < x; p++) {
                for (int b = 1; b < x; b++) {
                    double ans = Math.pow(b, p);
                    if (ans > x) {
                        break;
                    } else if(ans == x) {
                        largestP = p;
                    }
               }           
            }
    ...math.pow() is slow...any ideas...
    Regardless of the speed of Math.pow(), you are calling it way too many times.

    I mean, think about it: The outer loop is trying different values of p. (Note seems a little wasteful to start with p = 1, since all positive integer powers of 1 are going to be 1, so, why not start at 2?)

    Anyhow...

    The inner loop starts at b equal to 1 and goes all of the way up to x. Why? I mean for x = 9999991 (the largest prime less than million), it has to go through the inner loop that many times for that many values of b before going on to the next value of p. And it goes through the outer loop that many times (minus 1). That's lots of calculations.

    But...

    Think about it: If you have a value of b such that b to the power p is greater than x, you don't need to test any more values of b, right? Just break out of the inner loop.

    So: What is the maximum value of b that you have to test for a given value of x and P? If you can figure that one out, you can eliminate lots of time wasted in the inner loop that can't possibly give something useful.

    Well for (b to the power p) == x, we have p times log(b) == log(x), right.

    So the upper limit of the inner loop can be tested to see whether b is less than or equal to (you fill in the expression here)

    Equally importantly (actually, more importantly), if you reach the a value of p in the outer loop where the limit that we just calculated is 1, then not only do we not need to go through the inner loop at that point, but we can bail out of the outer loop, right? I mean, larger values of p would still not make us go through the inner loop, so you can quit right there!

    So, by my reckoning, for testing 999991 (and arriving at the conclusion that Pth = 1) the outer loop only has to go up through a value of p = 35, and the total number of times that Math.pow() is called is less than a couple thousand. (Compared with approximately 99998200000 that I think your original code would require.)

    For your specific number, 1073741824, the outer loop only needs to take p up to a value of 52 before it becomes unnecessary to go through the inner loop any more, and at that point it has found that Pth is equal to 30. (As a check, note that 2 to the power 30 is equal to 1073741824). The total number of times that Math.pow() is called is less than 35000.
    (Maybe you can think of ways to reduce calls to Math.pow() even more if you are still looking for "optimum" performance.)

    Your code with a couple of extra tests that save millions and millions (and millions) of calculations with Math.pow() for large values of x:
        public static int getPth(int x) {
            int largestP = 1;
     
            for (int p = 2; p < x; p++) {
                double limit = Math.exp(Math.log((double)x)/p);
                int ilimit = (int)Math.round(limit);
                System.out.printf("x = %d, p = %d, limit = %f, ilimit = %d\n",
                        x, p, limit, ilimit);
                if (ilimit < 2) {
                    break;
                }
                for (int b = 2; b <= ilimit; b++) {
                    double ans = Math.pow(b, p);
                    if (ans > x) {
                        break;
                    } else if(ans == x) {
                        System.out.printf("Setting largestP = %d\n", p);
                        largestP = p;
                    }
                }           
            }
     
            return largestP;    
        }


    Now, according to my precisely calibrated wink-o-meter, the time for the calculation of Pth(1073741824) is quicker-than-a-wink (a wink being approximately 50 milliseconds), but if you think you can do better than Math.pow() for getting values in the inner loop, there are a number of well known so-called "fast integer exponentiation" algorithms. You might start here: Exponentiation by Squaring - Wikipedia.

    Let us know if you find (or derive) something better than Math.pow() for this application. (But with integer arithmetic, beware of integer overflow. Even with longs instead of ints, beware. Java is deliberately designed in a way that integer overflows won't generate any exceptions or any other kind of automatic indication that results are not valid.)

    Cheers!

    Z
    Last edited by Zaphod_b; October 1st, 2012 at 09:00 PM.

  7. #7
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    [edit: code removed.]

    Basic jist/hint: Use my post above where I described methods for directly calculating b or p given the other.

    Algorithm 1:
    Given a known b, solving for p: If done right, this produces an O(n^(1/2)) algorithm. However, it performs badly if b is large.

    Algorithm 2:
    Given a known p, solve for b: If done right, this produces an O(log(n)) algorithm. Again it's slower for large b's, but this time it really isn't significant. Incidentally, I did make a mathematical error above (has since been corrected).

    It should be b = pow(x, 1 / p), not b = pow(x, -p).

    Benchmark results:

    compute Pth(1073741824) where p=30, 10000 times in a row.

    Algorithm 1: ~17ms
    Algorithm 2: ~21ms
    Zaphod's code: ~9170ms
    Original code: didn't bother, took too long to even get to 10 tries.

    Pth(1073741823) where p = 1, run 10000 times in a row:

    Algorithm 1: ~20568ms
    Algorithm 2: ~99ms
    Zaphod's code: ~9109ms
    Original code: didn't bother, took too long to even get to 10 tries.

    Moral of the story? Seek algorithm optimizations first before trying to micro-optimize things like the power function. I removed my code so you can have fun of trying to figure out how to implement it.
    Last edited by helloworld922; October 2nd, 2012 at 02:11 AM.

  8. #8
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    Quote Originally Posted by helloworld922 View Post
    ...Zaphod's algorithms look to be O(n log(n))...
    I tried to start with the Original Poster's code but with improvements and printout values that might lead to further improvement. It was intended to be the beginning, not the end of the investigation. I mean, I tried to put in a teaser to indicate further thought might improve things (like: Think about it: Why would we need the inner loop that was in the original code since we have already found a value that is as close as we can get? Just test it.)

    I didn't mean for it to be a challenge match, but a starting point.

    Oh, well...


    Cheers!

    Z
    Last edited by Zaphod_b; October 2nd, 2012 at 01:40 AM.

  9. #9
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Need a more efficient algorithm for finding the highest pth of a number.

    Sorry, I may have gotten a bit competitive. By no means am I saying your approach isn't valid, you still managed to make significant improvements and your thought process is very well explained.

    I think this is an excellent demonstration of how targeting algorithm complexity is almost always the best (and thus first) place to begin looking for optimizations.

    And I guess I did spoil the fun for the original poster... original post modified to hint at the potential but left the implementation as an exercise for the reader (only this time I did the exercise, too).
    Last edited by helloworld922; October 2nd, 2012 at 02:25 AM.

Similar Threads

  1. The nth highest number from a list
    By sbjibo in forum What's Wrong With My Code?
    Replies: 6
    Last Post: April 30th, 2012, 11:20 AM
  2. Finding Chromatic Number w/ Brute Force Algorithm
    By thecrazytaco in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 16th, 2011, 06:35 AM
  3. Finding Chromatic Number of a Simple Graph w/ Brute Force Algorithm
    By thecrazytaco in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 15th, 2011, 08:27 PM
  4. Finding the highest number in an array?
    By halfwaygone in forum Algorithms & Recursion
    Replies: 1
    Last Post: April 17th, 2010, 03:56 PM
  5. Inputing file (.txt) and finding the highest number in the file
    By alf in forum What's Wrong With My Code?
    Replies: 3
    Last Post: March 15th, 2010, 09:11 AM

Tags for this Thread