Why do I get an overflow in the total function? Shouldn’t I be able to call square(64ULL) inside the total() function? I pass the first 7 tests but not the last test 8. Here is my code.
#include "grains.h"
#include <vector>
#include <numeric>
#include <limits>
namespace grains {
long long unsigned square(long long unsigned square) {
long long unsigned grain {1};
for (int i = 1; i < static_cast<int>(square); ++i) {
grain *= 2ULL;
}
return grain;
}
long long unsigned total() {
// This line makes the test pass.
//return std::numeric_limits<long long unsigned>::max();
// This line fails the test 8.
return square(65ULL);
}
} // namespace grains
What is the maximal value that an unsigned long long can represent?
What is the “mathematical” value of square(65)?
Or put differently:
When square(65) gets called the for loop loops 64 times (1 to 65 exclusive). What’s the value of grain in the last two iterations of the loop?
I have changed the code because I thought I could solve the exercise.
The maximum value that a long long unsigned int can hold in C++ is 18,446,744,073,709,551,615.
Before I was getting this positive integer 9223372036854775808.
9223372036854775808 x 2 = 18446744073709551616
18446744073709551616 overflows the long long unsigned int type.
I added an index to the print out. The last two values now look like this:
63 -9223372036854775808
0
New code.
#include "grains.h"
#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
namespace grains {
long long unsigned square(int sqr) {
long long signed grain {1};
int index {0};
do {
std::cout << index << " " << grain << "\n";
grain *= 2;
index++;
} while (grain != 0);
return static_cast<long long unsigned>(grain);
}
long long unsigned total() {
return square(10);
}
} // namespace grains
int main() {
std::cout << '\n' << grains::square(64) << '\n';
return 0;
}
// OUTPUT
0 1
1 2
2 4
3 8
4 16
5 32
6 64
[...truncated...]
60 1152921504606846976
61 2305843009213693952
62 4611686018427387904
63 -9223372036854775808 // ????
0
In this second snippet you changed the type of the variable grain from unsigned long long to signed long long. Why that?
A signed long long can represent even fewer values that an unsigned long long, if it overflows you get undefined behavior (UB). In practice you get a negative value (-9223372036854775808).
You will have to find a way to implement the two functions without overflow (or in a way that an overflow does not affect the correct result).
The implementation of square() from your first snippet did that, it calculated the correct result for any of the 64 squares.
But when you call square(65) an unsigned long long cannot represent the mathematically correct value, you get 0.
Can you find an implementation of total() that does not call square(65)?