Data representation (part 2)

In this problem, you will implement the function ExponentToOverflow with parameters int init_value value and an unsigned int base. The function will multiply init_value by increasing powers of base (base^1, base^2, ..., base^(n-1), base^n) until integer overflow is observed. You can use pow from <cmath>. Should you do so, keep in mind pow returns a double; your program must perform integer arithmetic when multiplying the base raised to the exponent against the init_value.

ExponentToOverflow will return an std::pair<unsigned int, int> (you can use std::make_pair), where the pair's first field is the exponent that base was raised to that caused overflow when multiplied by int init_value. The pair's second field is the number observed when overflow occurred.

For example, if we invoked:

• ExponentToOverflow(1048, 2);
  • The implementation of ExponentToOverflow would multiply the original value 1048 by base 2 raised to increasing exponent values until overflow was observed.
  • On my machine, this occurred with exponent 21 and the overflow value observed was -2097152000.
  • That is, when we multiplied 1048 * 2^21, integer overflow was observed for the first time: exponents 1 through 20 inclusive did not cause overflow.
• ExponentToOverflow(-2000, 2);
  • The implementation of ExponentToOverflow would multiply the original value -2000 by base 2 raised to increasing exponent values until overflow was observed.
  • On my machine, this occurred with exponent 21 and the overflow value observed was 100663296 .
  • That is, when we multiplied -2000 * 2^21 , integer overflow was observed for the first time: exponents 1 through 20 inclusive did not cause overflow.
• ExponentToOverflow(-20000, 4);
  • The implementation of ExponentToOverflow would multiply the original value -20000 by base 4 raised to increasing exponent values until overflow was observed.
  • On my machine, this occurred with exponent 9 and the overflow value observed was -947912704 .
  • For this case, why is the computed overflow value negative when the starting value passed to this function is -20000? Consider that on my machine: -20000 * 4^8 = -1310720000 and -20000 * 4^9 = -947912704. Did you notice that -20000 * 4^9 evaluates to a less negative value than -20000 * 4^8? Consider that std::numeric_limits<int>::min() returns -2,147,483,648 and that -20000 * 4^9 should equal -5,242,880,000. Do you see what's going on? An int cannot store the result of -20000 * 4^9 since it's outside the type's range. Consider such cases for positive and negative init_values! You can do this by comparing the value you computed with exponent n to the value computed with exponent n - 1. If the result computed with exponent n has the same sign but is less than that computed with exponent n - 1, you've observed an overflow.