7
\$\begingroup\$

I have written this code which precisely calculates the nth power of x by a recursive method.

I compared my program with Java's pow(double, double) function, and most of the time I get comparable results, although sometimes pow is slow and the other times this program is slow.

Can anyone suggest any improvements or the way Java implements this function?

public double power(long x, int n) {

    double pow = 1L;
    if(n==0)
        return 1;
    if (n == 1)
        return x;
    if(n%2==0){
        pow = power(x, n / 2);
        return pow * pow;
    }
    else{
        pow = power(x,n/2);
        return pow * pow * x;
    }
}
\$\endgroup\$
  • \$\begingroup\$ gizmoworks.wordpress.com/sicp-exercises is the simplest to comprehend, but probably is not the fastest. \$\endgroup\$ – Leonid May 15 '12 at 3:23
  • \$\begingroup\$ Thank you, I was wondering that this can be done. Could you suggest me any link where I can read or find out, how to calculate product of two numbers(numbers are not necessarily powers of 2) with the help of binary shifting. PS: I know that any number can be represented as a sum of a(subscript)k * 2 ^ k when k running from 0 - n. \$\endgroup\$ – dharam May 15 '12 at 3:28
  • \$\begingroup\$ I took my words back. There must be some cool tricks though. \$\endgroup\$ – Leonid May 15 '12 at 3:29
  • \$\begingroup\$ martin.ankerl.com/2007/02/11/… \$\endgroup\$ – Leonid May 15 '12 at 3:30
  • 1
    \$\begingroup\$ Fractional exponents, e.g. 2 ** 0.5? \$\endgroup\$ – Wayne Conrad May 15 '12 at 16:32
6
\$\begingroup\$

The Java implementation of pow is implemented for double, rather than long, and probably uses logarithms. This makes direct comparison difficult - pow should have a more or less constant factor time, but double precision arithmetic can be expensive.

Otherwise, it seems reasonably straightforward.

If you're looking for speed, did you try using bit shifts rather than divides? It's possible that the compiler optimizes a divide by 2 to a bit shift, put possibly not. Though, the bit shift is probably somewhat less readable than the divide - and it is possible to be too clever.

\$\endgroup\$
  • \$\begingroup\$ Sorry! for the trouble num was for my own purpose to count the number of recursions. I have removed it now. \$\endgroup\$ – dharam May 15 '12 at 3:40
4
\$\begingroup\$

@Donals's suggestion was a good one. I do not check for overflow - I suppose an exception will be thrown then.

I did not try to compile and run this using Java. Please do try it yourself.

Note that fast code quickly starts to look ugly ...

Remember to properly measure the performance of your code. http://stuq.nl/weblog/2009-01-28/why-many-java-performance-tests-are-wrong

Also these two could be used to figure out if the number is a power of 2, and what that power is.

http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Integer.html#highestOneBit(int) http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Integer.html#lowestOneBit(int)

Basically, the lowest and the highest should be the same.

Here is an interesting and useful page: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

// Do you want to optimize for the worst case (2 ^ 1024) or the average case  / the ammortized cost??    
public static double power(long x, int n) {

    if (n == 0)
    {
        return 1;
    }

    if (n == 1) {
        return x;
    }

    // Something to think about - do you allow negative x ?
    if (x > -3 && x < 3) {
        return shortcutPower(x, n);
    }

    // TODO: Should finally check whether +/-n is some power of two,
    // and if so, then try to piggy-back on the binary shifting of 2.
    // I am not sure how long it takes to figure out which bit is set.

    return powerHelper(x, n);
}

private static boolean isPosOrNegPowerOfTwofast(int n) {
{
    return isPowerOfTwoFast(n) || isPowerOfTwoFast(-n);
}

// http://sabbour.wordpress.com/2008/07/24/interview-question-check-that-an-integer-is-a-power-of-two/
private static boolean isPowerOfTwoFast(int n) {
    return ((n!=0) && (n&(n-1))==0);
}

// No longer performs the checks every time ...
private static powerHelper(long x, int n) {
    double pow = power(x, n >> 1); // I bet Java compiler will generate the same bytecode as for / 2
    if (n % 2 == 0) {
        return pow * pow;
    }

    return pow * pow * x;
}

// You can keep on adding optimizations like these ... but remember to profile.
private static double shortcutPower(long x, int n) {
    if (x == 0) {
        return 0;
    }

    double sign = (n % 2 == 0) ? 1 : -1;
    if (x == 1 || x == -1) {
        return sign;
    }

    return sign * pow2(n);
}

// Please check this code
public static double pow2(int n) {
    double result = (1L << n % 60);
    while (n = n - 60 > 60) {
        result *= 1L << 60;  // I am sure that Java compiler can optimize this.
    }
}
\$\endgroup\$
2
\$\begingroup\$

These answers are correct if your result stays within the precision limit of the processor. The fallacy is assuming that a multiplication is O(1). It is not when your precision needs to exceed the built in precision.

When you multiply two 10 bit numbers, the algorithm used is a shift and add which must cycle across all 10 bits. If I were to raise a 10 bit number to the 8th power, it would take 70 shifts and adds using a short loop which multiplies the result by the number 7 times.

Using the power algorithm that reduces the steps by half each time, actually doubles the amount of work that it must do. Raising the same 10 bit number to the 8th power will yield: 10 shifts and adds to get X*X. But now X is a 20 bit number needing to be raised to the 4th power. Next time through takes 20 shifts and adds, with X resulting in a 40 bit number that needs to be squared. The last pass takes 40 shifts and adds and X is the result. Adding the passes up, 10 + 20 + 40, is 70 shifts and adds.

This is no more efficient than using a simply multiplication loop.

\$\endgroup\$
1
\$\begingroup\$

You're missing a case for n < 0. Either return 1.0 / power(x, -n); or delegate to Math.pow() in that case.

\$\endgroup\$
1
\$\begingroup\$

Few notes:

  • Formatting

    1. Spacing. if(n==0) and if (n == 1).
    2. Braces: Though optional for single statements but most prefer it to be there. Your choice.
  • Naming: Though its a simple method but we could use variables like base, exponent.

  • Can pow store LONG_MAX ^ INT_MAX ? If not should we use Long and throw exception for out-of-range cases?
  • Since the power is an int , would you like to handle negative powers as well or a check for n<0 is required?

Another algorithm you can resort to:

// 10^5(101 base 2) = 10^ (4 + 1) = 10^1 * 10^4 = 10000.
public static long power(long base, int exponent){
    long result = 1;
    long pow = base;
    while(exponent>0){
        if((exponent & 1) == 1){
            result *=pow;
        }
        pow*= pow;
        exponent = exponent>>1;
    }
    return result ;
}

Its significantly faster than Math.pow(). Ideone link.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.