Thread: 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.

What does it mean to get 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

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

Originally Posted by firstTimeJava

        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

[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.

Originally Posted by helloworld922

...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

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).