Find power of a number

Question

Looking for optimization, smart tips and verification of complexity: O (log (base 2) power).

NOTE: System.out.println("Expected 16, Actual: " + Power.pow(2, 7)); is a typo. It correctly returns 128.

/** * Find power of a number. * * Complexity: O (log (base 2) power) */ public final class Power { private Power() { } /** * Finds the power of the input number. * @param x the number whose power needs to be found * @param pow the power * @return the value of the number raised to the power. */ public static double pow(double x, int pow) { if (x == 0) return 1; return pow > 0 ? getPositivePower(x, pow) : 1 / getPositivePower(x, -pow); } private static double getPositivePower(double x, int pow) { assert x != 0; if (pow == 0) return 1; int currentPow = 1; double value = x; while (currentPow <= pow/2) { value = value * value; currentPow = currentPow * 2; } return value * getPositivePower(x, pow - currentPow); } public static void main(String[] args) { System.out.println("Expected 6.25, Actual: " + Power.pow(2.5, 2)); System.out.println("Expected 16, Actual: " + Power.pow(2, 7)); System.out.println("Expected 0.25, Actual: " + Power.pow(2, -2)); System.out.println("Expected -27, Actual: " + Power.pow(-3, 3)); } }

I assume you don't want to use the built-in java.lang.Math.pow function. — ChrisW
– ChrisW, Commented Jan 14, 2014 at 0:27

Vedran Šego · Accepted Answer · 2016-08-03 13:09:41Z

This can get worse than \$\operatorname{O}(\log \verb~pow~)\$. [Remark: in \$\operatorname{O}\$-notation, the base of an logarithm is irrelevant, since it represents only a multiplication with a constant]

Let \$\verb~pow~ = 2^n - 1\$ for some \$n\$. Then you're computing the following powers:

\$1, 2, 4,\dots, 2^{n-1}\$, followed by a function call for \$\verb~pow~ = (2^n-1) - 2^{n-1} = 2^{n-1} - 1\$;
\$1, 2, 4,\dots, 2^{n-2}\$, followed by a function call for \$\verb~pow~ = (2^{n-1}-1) - 2^{n-2} = 2^{n-2} - 1\$;
\$1, 2, 4,\dots, 2^{n-3}\$, followed by a function call for \$\verb~pow~ = (2^{n-2}-1) - 2^{n-3} = 2^{n-3} - 1\$;
...

All in all, \$n + (n-1) + ... + 1 = n(n+1)/2\$ calls of the inner loop. In terms of pow, this is \$\operatorname{O}(\log^2 \verb~pow~)\$.

Instead, observe pow as a binary number. I don't do Java, so I'll just sketch this in C, which is quite like it.

double px = x; // current power of x double result = 1; while (pow > 0) { if (pow % 2) result *= px; pow /= 2; px *= px; }

So, you are observing \$x, x^2, x^4, x^8,...\$ and multiplying with them if the corresponding binary digit of pow is equal to \$1\$. This has \$\operatorname{O}(\log \verb~pow~)\$ steps.

By the way, I don't think \$2^7\$ is expected to be \$16\$. ;-)

I added some MathJax to this answer (the edit's in the queue right now) but I'm unsure how you want MathJax for that big code block starting with 1, 2, 4,..., 2^{n-1}. Can you edit it the way you want to do it? — bb216b3acfd8f72cbc8f899d4d6963
– bb216b3acfd8f72cbc8f899d4d6963, Commented Aug 3, 2016 at 3:14
@Peanut Thank you. I've TeXified it now (that was not an option when I first wrote the answer). Feel free to suggest further improvements if you think I did something wrong or unclear. — Vedran Šego
– Vedran Šego, Commented Aug 3, 2016 at 13:13

rolfl · Accepted Answer · 2014-01-14 00:57:09Z

Bug #1: 0.0ⁿ where n > 0 is equal to 0.0, and not 1 as you have in your code if (x == 0) return 1; (although 0⁰ is 1, not 0, and 0.0ⁿ where n < 0 is NaN).

Bug #2: You very carefully have the test method:

System.out.println("Expected 16, Actual: " + Power.pow(2, 7));

But, 2⁷ is actually 128.

At this point, I figure a vote-to-close, but, FYI:

Picking apart the core method getPositivePower(double, int) .... This is your code:

private static double getPositivePower(double x, int pow) { assert x != 0; if (pow == 0) return 1; int currentPow = 1; double value = x; while (currentPow <= pow/2) { value = value * value; currentPow = currentPow * 2; } return value * getPositivePower(x, pow - currentPow); }

Why do you need the assert? Sure, you can check the input value is correct, but, there is only one place to call the method, and it is a few lines above. There is no reason to assert everything.... you have to trust something somewhere, and in my opinion, this is overly cautious.
in the last line, you are either 1, or 0 powers short of your intended result, so why do you have to do a full recursion? Simply: `return value * (pow == currentPow ? 1 : x);

Stack Exchange Network

Find power of a number

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Find power of a number

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions