1

I need to operate on 64bit integers. I am trying to get the result of 36 raised to the power of 12 as an exercise (and as a requirement).

I've used unsigned long long for 64 bit integer on my VS2008 compiler. I've made the code below and can someone explain to me, why my for loop version produces incorrect results while my recursive version of the Power function produces correct result?

FYI: 36 raised to 12 is 4738381338321616896

template< typename _T1, typename _T2 >
_T1 Power( _T1 p_base, _T2 p_power )
{
    /*
    // This produces 0?!!
    if( p_power == 0 ) return 1;
    for( _T2 i = 1; i < p_power; ++i )
    {
        p_base *= p_base;
    }

    return p_base;
    */

    // This produces correct result.
    if( p_power == 0 ) return 1;
    if( p_power == 1 ) return p_base;

    return p_base * Power( p_base, p_power - 1 );
}

void main( int argc, char * argv[] )
{
    unsigned long long charsetSize = 36LL;
    printf( "Maximum Keys: %llu\n\n", Power( charsetSize, 12 ) );

    system( "pause" );
}
MrHuggies
  • 181
  • 1
  • 2
  • 8
  • `_T1` and `_T2` are **reserved**, [don't use them](http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier). Just do what everyone else does and use `T` and `U`. – GManNickG Nov 11 '10 at 06:31

3 Answers3

5

You're squaring the result at each iteration. It should be something like:

_T1 result = 1;
for( _T2 i = 0; i < p_power; ++i )
{
    result *= p_base;
}

Note that if you write the loop like this, the p_power == 0 check is unnecessary.

Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
  • @all: Doh! I overlooked that. Thanks everyone. I was expecting it was some sort of 64 bit capacity or a template argument resolution issue and it was the algorithm that was wrong after all! (cross-eyed) – MrHuggies Nov 11 '10 at 04:35
1

This is because you are storing the result of each multiplication in p_base. This is probably causing the variable to overflow.

You need to store the input value for p_base and the "working" variable separately. By the for loop's logic, 2 to the power of 4 is 65536.

cdhowie
  • 158,093
  • 24
  • 286
  • 300
1

p_base *= p_base;

This is incorrect. The result gets squared after each iteration

Correction

_T1 pow = 1LL;
for( _T2 i = 1; i <= p_power; ++i )
{
    pow *= p_base;
}
return pow;
Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345