6
\$\begingroup\$

Implementation:

This works based on this observation:

$$a^n = a^{n/2} * a^{n/2}$$

BigInteger Pow(BigInteger x,int n)
{
    if(n == 0) return 1;
    else if(n % 2 == 0) {
        var val = Pow(x,n/2);
        return val * val;
    }
    else return x * Pow(x,n-1);
}

How can I improve this? Is there a more efficient algorithm?

\$\endgroup\$
  • 2
    \$\begingroup\$ You can skip the else and just keep the return x * Pow(x,n-1); And pleeeease allow the method parameters to breath so your code is more readable. \$\endgroup\$ – Heslacher Nov 10 '14 at 17:24
  • 5
    \$\begingroup\$ Why don't you use BigInteger.Pow static method? msdn.microsoft.com/en-us/library/… \$\endgroup\$ – CharlesNRice Nov 10 '14 at 17:29
  • 1
    \$\begingroup\$ You could use a loop instead of recursion, but given that most of the work will be done in the calculations, there isn't much point in optimising that. \$\endgroup\$ – Guffa Nov 10 '14 at 20:04
  • 1
    \$\begingroup\$ BigInteger has a property IsEven, so you don't need the n % 2 \$\endgroup\$ – Dennis_E Nov 10 '14 at 21:02
  • 2
    \$\begingroup\$ There's an infinite loop if n=-1. Should probably just error for negative n. \$\endgroup\$ – Michael Anderson Nov 11 '14 at 4:57
6
\$\begingroup\$
  • Don't use Egyptian style bracing, that is the style more widely accepted by Java, use the more widely accepted C# bracing style.

Your current structure for the if/else statements is not good. If you have to use braces in the else/elseif statements then you should use bracing everywhere, even on a single operation inside the if statement

like this

BigInteger Pow(BigInteger x,int n)
{
    if(n == 0) 
    {
        return 1;
    }
    else if(n % 2 == 0)
    {
        var val = Pow(x,n/2);
        return val * val;
    }
    else
    {
        return x * Pow(x,n-1);
    }
}

Use if statements like this without the else if

BigInteger Pow(BigInteger x,int n)
{
    if(n == 0) return 1;
    if(n % 2 == 0)
    {
        var val = Pow(x,n/2);
        return val * val;
    }
    return x * Pow(x,n-1);
}

You return inside the if statements so there is no need to else anything just if through because if the first one is true then none of the other if statements will be executed.


I needed to change BigInteger to long. BigInteger it still an INT and so is long, for some reason I could not use BigInteger, so in my equations I will use long

Your naming should definitely be better I went with numBase and numPower I don't normally like hungarian style notation like this, but base is kind of reserved and all.

this is what mine looks like

public static long Pow(long numBase, long numPower)
{
    if (numPower == 0)
    {
        return 1;
    }
    if (numPower % 2 == 0)
    {
        var val = Pow(numBase, numPower / 2);
        return val * val;
    }
    return numBase * Pow(numBase, numPower - 1);
}

also I went with a static method inside of a static class so I could just call it willy-nilly whenever I felt like it. Like this:

Class1.Pow(numBase,numPower);

the only thing with this is that it looks like you are overloading the already created Math.Pow method, you should probably at the least Comment to that effect, and/or create an actual overload for Math.Pow

\$\endgroup\$
  • 3
    \$\begingroup\$ The C# syntax doesn't specify how you should place braces. You can advocate any style you like, but it's not "C# syntax". \$\endgroup\$ – Guffa Nov 10 '14 at 19:56
  • 3
    \$\begingroup\$ @Guffa, the Egyptian style of bracing is widely accepted as the Java bracing style, where the other style is widely accepted as C# bracing style. \$\endgroup\$ – Malachi Nov 10 '14 at 20:07
  • 2
    \$\begingroup\$ let's get the General consensus from Chat, there are others that would support my view and they would probably have better reasons as well, The Second Monitor \$\endgroup\$ – Malachi Nov 10 '14 at 21:57
  • 2
    \$\begingroup\$ When in Rome do as the Romans @Guffa. C# devs expect their braces a certain way. While consistency within a code base is more important than conforming to a particular style, it certainly is nice to write code that peers are comfortable with. \$\endgroup\$ – RubberDuck Nov 10 '14 at 22:35
  • 1
    \$\begingroup\$ Brace style is IMHO an entirely stylistic issue. So long as the code is consistently braced then you should concentrate on the content and not the style. \$\endgroup\$ – Alnitak Nov 11 '14 at 2:57
3
\$\begingroup\$

Consider using iteration instead of recursion. Here's an example with short variable names (p for power, b for base, r for result) and compact if statements (to make code easier to read).

Boolean array in first loop keeps track of what kind of multiplication to apply in the second loop. Using long allows for results up to 10^18 (or 2^62) before overflowing.

public static long Pow(int b, int p)
{
    if (p < 0) return -1;   // p must be positive
    if (p == 0) return 1;

    bool[] a = new bool[p/2 + 2];
    int i = -1;
    while (p > 0)
    {
        if (p % 2 == 0) { a[++i] = true;  p /= 2; }
        else            { a[++i] = false; p--;    }             
    }

    long r = b;
    while (i-- > 0)
    {
        if (a[i]) { r *= r; }
        else      { r *= b; }
    }
    return r;
}

Adding less optimal single loop iterative code example for comparison as mentioned in comments. In case of 2^15 Pow does 6 multiplications and PowUp does 10.

public static long PowUp(int b, int p) // not optimal
{
    if (p < 0) return -1;   // p must be positive
    if (p == 0) return 1;

    long r = b;
    int i = 1;
    while (i < p) 
    {
        if (i * 2 < p) { r *= r; i *= 2; }
        else           { r *= b; i++;    }              
    }
    return r;
}
\$\endgroup\$
  • \$\begingroup\$ Allocating a new array to calculate pow seems "excessive". There's no need for that even in an iterative form. \$\endgroup\$ – Michael Anderson Nov 11 '14 at 4:59
  • \$\begingroup\$ Iterative form with a single loop is less effective as it requires more steps between p/2 and p. 2^15 requires only 6 multiplications using code above and 10 multiplications in case of single loop implementation (see PowUp method above). \$\endgroup\$ – Andrej Nov 11 '14 at 7:52
  • 1
    \$\begingroup\$ Except you're not counting the 5 divisions and 5 mod operations in the first case - which brings the operation count back to about par. And then the array allocation would usually completely dwarf all of that anyway. (Depends on whether the compiler can optimize the allocation away entirely...) \$\endgroup\$ – Michael Anderson Nov 11 '14 at 8:29
  • 1
    \$\begingroup\$ Agreed. It starts to make a difference for bigger powers [O(logN) vs. O(N)]. \$\endgroup\$ – Andrej Nov 11 '14 at 8:59
3
\$\begingroup\$

I agree with @Malachi's coding style suggestions. While you can customize Visual Studio to make up your own styling convention in a very flexible way, I find it better when people adapts to the language's most used / popular styling conventions for mainly two reasons:

  1. Your code formatting will homogeneous among all your projects by default;
  2. The code you post on Q&A websites and forums will not get criticized about the formatting and people reformatting your code for lisibility on these websites will not have an hard time doing it.

There is actually a C# coding style used by most developers at Microsoft and it has a long history:

The main idea behind this style is to ensure consistency.

When you enforce braces on their own line everywhere (in method blocks, conditional blocks, etc.) it becomes easier and quicker to read and understand, for everybody.

I bet you would be quickly criticized by most Java developers if you were posting Java code without the Egyptian braces style. Every language has its founding coding conventions.

\$\endgroup\$
  • \$\begingroup\$ Egyption-style bracing essentially compels the use of a brace-pair for all conditionals, even those which control only a single statement, while open-brace-on-own-line style makes it much safer to have a conditional control a single statement. Effectively, then, Egyptian-style saves a line every time a control statement affects multiple statements, but costs a line in many cases where a conditional affects just one statement. \$\endgroup\$ – supercat Nov 10 '14 at 23:30
  • 2
    \$\begingroup\$ I didn't mean that a style is better than another. My point is it's better to stick to the original coding convention of that language. And above all, don't mix coding conventions throughout the same code base. \$\endgroup\$ – user57782 Nov 10 '14 at 23:32
  • 2
    \$\begingroup\$ There is no original coding convention for C#. The automatic formatting was introduced in VS 2008, when people had been writing C# code for five years already. \$\endgroup\$ – Guffa Nov 11 '14 at 0:03

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.