Squaring number in c++, Kaprekar numbers [duplicat

Question

This question already has an answer here:

• Multiplication of two integers in C++ 3 answers

Found this issue in C++ while detecting Kaprekar numbers in a range. For number 77778 -

unsigned long long sq = pow(n, 2);

returns 6,049,417,284 while

unsigned long long sq = n * n;

returns 1,754,449,988

Any ideas why? Is this some sort of overflow which pow avoids but normal n*n does not.

Answer 1

I suspect that n is declared as unsigned int and you've compiler with a data model that assumes int to be 32 bits wide. The maximum value that can be represented with this type would be 2³² - 1 = 4294967295. Anything beyond this value would wrap around. So assigning 4294967296 would become 0, 4294967297 would become 1, and so on.

You have an overflow; since both operands are unsigned int the resulting type would be the same too. The true result of the operation would be 6049417284. Assigning it to an unsigned int would (wrap) and become 1754449988 = 6049417284 - 4294967296. This unsigned int result is assigned to a wider type unsigned long long, which doesn't change the value. It's necessary to understand the difference between the result's type (the type of the expression) and destination type (the type of the variable that is going to hold the result).

Wrap around behaviour (more formally modulo n) in unsigned types is well-defined in C++, so the compiler might not warn you.

Quote from Unsigned Arithmetic:

If an unsigned integer overflows, the result is defined modulo 2^w, where w is the number of bits in that particular unsigned integer. By implication, an unsigned integer is never negative.

Answer 2

Assuming your n to be typical int or unsigned int, the reason for this is because

this line

unsigned long long sq = n * n;

is equivalent to

unsigned long long sq = (int)(n * n);

as the n * n will be first processed (both as integers) before assigning the result to sq. So, this is an overflow problem (And welcome to Stack Overflow too!).

You also probably want to understand these terms overflow and casting more by searching around (since they are very common issues in Computing, understanding them early will be of great help!).

This has nothing to do with Kaprekar numbers. In most of nowadays machine int is 32-bit. Thus it can only handle value -2,147,483,648 to 2,147,483,647 (or 0 to 4,294,967,295 for unsigned integer counter part).

Thus processing n * n will give you:

n * n = 6,049,417,284 - 4,294,967,296 = 1,754,449,988 //overflow at (4,294,967,295 + 1)!

If you do casting before hand:

unsigned int n = 77778;
unsigned long long sq = pow(n, 2);
unsigned long long sq2 = (unsigned long long)n * n; //note the casting here.
std::cout << sq << std::endl;
std::cout << sq2 << std::endl;

Then the results will be identical, since there won't be overflow.

Answer 3

Your n is declared as a 32 bit int. You need to either change it to long long or just typecast the operation into long long.

unsigned long long sq=(unsigned long long)n*n;

this will give the right answer