Computing Power yourself: when, why and how

Computing x raise to power y yourself and its need

This is a pretty trivial thing to do as many would say. But there is an even subtle question. Why would you imagine coding one on your own because a pretty good library function already exists? Right?

Well, there are scenario’s (though not very frequent, but practical enough to code it) when your library function would fail. Let’s take a closer look.

The prototype given in cmath header file is either

double pow ( double base, double exponent );

Or a variation such as taking the exponent as int or returning a long double instead.
pow - C++ Reference

One fact that I want everyone to remember at this point is “Precision of integer portion of every double or long double is approximately 15 digits” as quoted here
Variables. Data Types. - C++ Documentation

which is the source of my problem. A few relevant posts are listed.

http://forum.codecal...-power-2-c.html
http://forum.codecal...point-help.html
http://forum.codecal...-vs-double.html

Let me go deeper.

An int on 32 bit machine is 4 bytes and a long int is usually the same. However, there is another data type available i.e. long long int on gcc/Linux or __int64 on windows. This is an 8 byte integer. Also an int on 64 bit platforms would be 8 bytes.

What if you were using an 8 byte data type on a 32 bit machine (or 64 bit but it didn’t have a corresponding precise enough power function)? An 8 byte integer is about 19 digits for signed ranges and 20 for unsigned.

Now imagine if you have a base and exponent whose result is 19 digits long integer, is your standard function returning double or long double that can approx 15 digits (rest goes into fraction) going to produce correct results? No, it will be 3-4 digits short on precision and even a narrow initial range of fifth digit for unsigned values.

In such a scenario you need to write a power function on your own.

A few supporting examples, plain c++ code computing powers


    long double base = 23;

    int exp = 13;

    long double res = pow(base, exp);

    unsigned __int64 res_int = res;   // this is windows / Visual studio specific


    // Following can be used for Linux instead of above

    //long long int res_int = res;

    

    cout.precision(18);


    for (int i=0; i<5; i++)

    {

        res = pow(base, exp);

        res_int = res;

        cout << "base : " << base << " Exponent : " << exp << endl;

        cout << "Long Double result : " << res << endl;

        cout << "Long    Int result :  " << res_int << endl;

        base += 1;

        //exp += 2;

    }

power1.jpg 54.43K 25 downloads

I guess the loss of digits if “Integer part is over 15 digits and up to 18” is obvious. This is significant when the numbers are not fractional and it is NOT some fractional part we are losing. The above examples clearly mean that our results could be off by up to 1000 as an integer value (as in last two examples).

The solution of course is to have a function which operates using long long ints only. Though its range would certainly be much smaller than that of doubles. But it’s precision in terms of digits would be higher.

Following is the power function


__int64 power(int base, int exp)

{

    __int64 product = 1;


    for (int i=0; i<exp; i++)

        product *= base;


    return product;

}

Following changes are made in the for loop in main to compute, compare and display results.


        res = pow(base, exp);

        res_int = power(base, exp);

        //res_int = res;

Also the output of Double result from library pow function vs. output of our own power function is given below for the same five inputs used earlier.

power2.jpg 54.26K 57 downloads

Now there can be optimizations to this power function such as instead of looping exponent times, it could increase exponentially i.e. instead of multiplying 2 ten times, after multiplying once it got a result 4 which is already 2 times 2. Multiplying 4 with 4 if it is less than the total exponent required would only make this function faster because of running lesser iterations. Code follows:


unsigned __int64 power(int base, int exp)

{

    unsigned __int64 product = base;


    for (int i=1; i<exp;)

    {

        if(i*i <= exp)

        {

            product *= product;


            if(i == 1)

                i++;


            else

                i *= i;

        }


        else

        {

            product *= base;

            i++;

        }

    }


    return product;

}

Also some sample output calculations to prove the above function produces the same results as earlier but is faster as visible in the code.

power3.jpg 44.42K 29 downloads

fayyazlodhi said:

// Following can be used for Linux instead of above
//long long int res_int = res;

That's, as far as I know, a GCC-specific compiler extension, not the standard for GNU/Linux. long long is ANSI Standard C99, so as long as you have a C99 compliant C compiler, it should compile universally. However, long long is not ISO C++, since C++ is based on C89 (for all practical purposes C90), but GCC supports it as an extension. MS Visual C++ hasn't implemented C99, but of popularly demanded features they have implemented similar ideas (just using different keywords to promote vendor lock-in). Why not use a simple define?

#if !defined(__int64) && defined(__GNUC__)

#    define __int64 long long

#endif

Use #define instead of typedef so you can use unsigned __int64 and it'll work.

EDIT:
I believe best solution though is stdint.h if your compiler supports it (MSVC++ usually doesn't, here's fully compliant header implementation), then use uint64_t.

Edited by ZekeDragon, 12 June 2011 - 07:10 AM.