Run time error binary exponentiation

[roknroll3r]

Hi all
I am new to programming and I believe I have there is a run time error in this custom function (left to right binary exponentiation). Can you please help me to understand the code so I can see the solution. I believe it has to do with the memory not too sure as i am only a beginner. Any help is welcomed. Thanks

double mypow(double base, int exponent)
{
int k;                    /* A counter that initially gets set to the bitlength of exponent (and counts down afterwards) */

int kpow;                /* A variable that will always equal 2 to the power k */

double result;                /* Will hold intermediate and final result of the exponentiation */

int n;                  /* Will hold the part of the exponent that still needs to be processed */

/* If the exponent is negative, make a recursive call (once) */
    if (exponent<0);
    {
        return 1/mypow(base, -exponent);
    }

/* Determine the bitlength of the exponent, i.e. the smallest k s.t. exponent < 2^k */
    k = 0;
    kpow = 1;
    while (kpow<exponent)
    {
        kpow *= 2;
        k++;
    }

/* Assume that the exponent equals 2^l a_l + ... + 2 a_1 + a_0

     * Then left-to-right exponentiation will process the bits from a_l down to a_0

     * Algorithmic invariant: result^(2^k) * base^n = base^{exponent} and 0<=n<2^k

     */

/* Initialize the result and remainder of exponent */
    result = base;
    n = exponent;

/* Process the exponent from left to right */
    while ( k>0 )
    {
        kpow /= 2;
        k--;

/* square */
        result *= result;

/* check if bit a_k is set or not */
        if ( n>=kpow )
        {
/* bit to process is set */
            printf("1");

/* multiply in the base */
            result *= base;

/* update the exponent to reflect bit has been processed */
            n -= kpow;
        } else {
/* bit to process is not set */
            printf("0");
/* no further work needed */
        }
    }

    return result;
}

[Matticus]

If you're asking for help to understand the code, then I'm guessing you didn't write it yourself.

Normally, the best way for a beginner to understand functions like this is to go through the code, step by step, and see what it is doing, using a pencil and paper to keep track of values as you're doing so.

However, this function appears to be garbage. There is one clear issue right from the start:

if (exponent<0);
{
    return 1/mypow(base, -exponent);
}

See the semi-colon after the "if()"? That doesn't belong there. To the compiler, the code looks like this:

if (exponent<0)
    ;

{
    return 1/mypow(base, -exponent);
}

A semi-colon by itself is a "null statement" - that is, a statement that does nothing (like a NOP in assembly). So the following "return" will always be executed. This return includes a recursive call ... but there does not appear to be a proper exit condition for the recursion.

Based on this bit alone, I'm not willing to dig any deeper into this code. Do yourself a favor and forget about this function.

[vart]

1. You should pass your code as text

#include <stdio.h>

double mypow(double base, int exponent)
{
    int k;                    /* A counter that initially gets set to the bitlength of exponent (and counts down afterwards) */

    int kpow;                /* A variable that will always equal 2 to the power k */

    double result;                /* Will hold intermediate and final result of the exponentiation */

    int n;                  /* Will hold the part of the exponent that still needs to be processed */

    /* If the exponent is negative, make a recursive call (once) */
    if (exponent<0);
    {
        return 1/mypow(base, -exponent);
    }

    /* Determine the bitlength of the exponent, i.e. the smallest k s.t. exponent < 2^k */
    k = 0;
    kpow = 1;
    while (kpow<exponent)
    {
        kpow *= 2;
        k++;
    }

    /* Assume that the exponent equals 2^l a_l + ... + 2 a_1 + a_0

    * Then left-to-right exponentiation will process the bits from a_l down to a_0

    * Algorithmic invariant: result^(2^k) * base^n = base^{exponent} and 0<=n<2^k

    */

    /* Initialize the result and remainder of exponent */
    result = base;
    n = exponent;

    /* Process the exponent from left to right */
    while ( k>0 )
    {
        kpow /= 2;
        k--;

        /* square */
        result *= result;

        /* check if bit a_k is set or not */
        if ( n>=kpow )
        {
            /* bit to process is set */
            printf("1");

            /* multiply in the base */
            result *= base;

            /* update the exponent to reflect bit has been processed */
            n -= kpow;
        } else {
            /* bit to process is not set */
            printf("0");
            /* no further work needed */
        }
    }

    return result;
}

And do not run your program till you fix all warnings. Especially this nasty one

test.c(68): warning C4717: 'mypow' : recursive on all control paths, function will cause runtime stack overflow

[grumpy]

And do not run your program till you fix all warnings. Especially this nasty one

test.c(68): warning C4717: 'mypow' : recursive on all control paths, function will cause runtime stack overflow

That warning is spurious for this code. The function is only recursive if exponent is negative, and only one level deep.

To respond - somewhat - to the OP

1) This code will not cause a runtime error unless an overflow or underflow occurs. If you are correct in your belief that you have a runtime error in this function, you need to check the arguments your code is passing.

2) All the code is doing is using the logic that any exponent is the sum of a number of powers of two.

[Matticus]

The function is only recursive if exponent is negative

As I noted in post #2, there is a logic error which will always result in that recursive call.

[grumpy]

As I noted in post #2, there is a logic error which will always result in that recursive call.

Yeah, okay. Semi-colon.