(C++) 4^20 problem

[anndurill]

Hey guys,

I'm a total newbie and I suck at programming. I have following problem:
For CompSci. class we have to create a prog which can calculate power 20 of a user defined variable. It has to be achieved with (max. 5) multiplications, not with any other functions.
It works fine for almost any base, I tested up to 13^20. However, it does not work for base values 4,8,12....
It can calculate 4^8, 8^8, 12^8, but anything greater (^16..^20) will give 0 as output. The problem is only occurring with these bases and these high powers.
I have no idea why and I'm frustrated. Thanks for any help.

#include <iostream> 

int main()
{
  // input variable a
  std::cout << "Compute a^20 for a =? ";  
  unsigned int a;
  std::cin >> a;

  // computation
  unsigned int b = a * a; 	// b = a^2
  unsigned int c = b * b;	// c = a^4
  std::cout << c << ".\n";

  unsigned int d = c * c;	// d = a^8
  std::cout << d << ".\n";

  unsigned int e = d * d;	// e = a^16
  std::cout << e << ".\n";

  unsigned int f = e * c; 	// f = a^20
  std::cout << f << ".\n";
  

  // output a^20 ("f")
  std::cout << a << "^20 = " << f << ".\n";
  return 0;
}

[MiiNiPaa]

4^20 is 1 099 511 627 776
However unsigned int is probably 32 bit long and can only hold numbers up to 4 294 967 295

So extra information will get cut off. As computers work in binary, we should look how 4^20 represented in binary.
It is 1 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000. As uint is only 32 bit long, only lower 32 bits will be stored. I highlited them. As you can see the are all 0 so resulting value is 0. You can use unsigned long long which can hold values up to 18 446 744 073 709 551 615 here.

[48T7M4Gy]

You have reached the limits of 'int'. What you need is 'long int' and 'long long int' instead.
http://www.cplusplus.com/reference/climits/

[Smac89]

Are you sure there is no range to this "user defined variable"? Although using unsigned long long long will give you an extra 64 bits to work with, but calculations like 20²⁰ (104857600000000000000000000) or even 13²⁰ (19004963774880799438801) will require more than 64 bits to represent.

http://web2.0calc.com/

[anndurill]

First of, thank you all for your help so far. :)

What I still don't understand is, why the program with unsigned int is capable of calculating 13^20 etc, but not any of the numbers dividable by 4 (4^20, 8^20, 12^20...)
If it was just a matter of "space" to store the values, calculations of 9^20, 13^20 or even 5^20 shouldn't work either, but they do....? That's so weird

[MiiNiPaa]

why the program with unsigned int is capable of calculating 13^20 etc, but not any of the numbers dividable by 4 (4^20, 8^20, 12^20...)

It does calculates all of them. Result just ges cut. Result of exponentation of number divisible by four has 0 as lowest 32 bits and that number is displayed. Other numbers got lucky and have some other bits set. It does not chacge the fact that the result is wrong. Get a calculator and see for yourself.

To illustrate what happens: do calculations I ask and write onlt two last digits of the result:
1) 10^5
2) 2^9
See what you got in both cases.

[anndurill]

Thank you very, much now I get it.
I managed to get correct, uncut results up to 8^20 with unsigned long long.