Description
So I was originally planning on not giving you kiddos an assignment this week; I was super excited. No grading. No emails. No “Did you include iostream? Are you sure? You might want to check if you included iostream. Naw just double check, I’ll wait. . . Oh you did? Really?! Crap.” So suddenly I had this free weekend, and as I do with every free weekend, I busted out C++ and started running code (social life’s not going so hot…) and I tried the following: **** #some crazy includes #using stds (but like, the good kind) int main() { int i=2147483647; i+=2; cout<<“This is should be 2147483649. (Maybe it’ll be my friend…): “<<i<<endl; return i; } **** And then I compiled it, no errors, and ran it and got the following in my terminal: Figure 1: Finding Friendship? So I was expecting 2147483649, and I got -2147483647. Whatevs ya’ll, computers can’t be perfect. Ain’t. no. thang. Frealz, I’m only off by 4294967296. Pshht drop in the bucket for laid back people like us right?! But then I got to thinking, even though this error is super trivial and so tiny no one would ever notice it, what the H is going on?! Well, a cursory google search gives us this – the minimum and maximum values for a signed int (i.e. signed meaning the int can be positive or negative): Figure 2: The Limits Of Friendship? Looking past the astonishing coincidence that the number I tried to add to just so happened to be the upper limit of signed ints in C++, Why did we get such a weird solution in the terminal above?! The answer lies in the term “integer overflow.” From Wikipedia: *** If the variable has a signed integer type, an overflow can cause its value to wrap and become negative. This overflow violates the program’s assumption and may lead to unintended behavior. Similarly, subtracting from a small unsigned value may cause it to wrap to a large positive value which may also be an unexpected behavior. Multiplying or adding two integers may result in a value that is nonnegative, but unexpectedly small. If this number is used as the number of bytes to allocate for a buffer, the buffer will be allocated unexpectedly small, leading to a potential buffer overflow.**** So for signed ints, if we go over that max int value in Figure 2, we wrap around to the negative side. Technically speaking, for signed ints in C++ the behavior is undetermined which means it usually wraps around but it’s not guaranteed to. If you didn’t understand that don’t worry, just know that our ints have a hard cap. A total aside: An int is 4 bytes, each byte has 8 bits (8*4=32), so we can actually calculate this hard cap number. We can figure the total number we can represent by taking 2 to the 32 (because each bit can be 1 or 0, we have 32 bits) and then dividing by 2 (i.e. dividing this guy “equally” among the negative and positive numbers). Figure 3: Limits on Friendship 2? So in this assignment we are going to make a new type (i.e. a new class) called “bigInt” that allows us to theoretically have a number that is 2147483648 DIGITS LONG (for comparison, that number in Figure 3 is only 9 digits long). There are many ways we can implement this. Our basic strategy will be to store each digit as a dynamically allocated cstring array that resizes to the amount of memory we need (you need to include <cstring, you can read about cstring on pages 197 tells you what they are (i.e. how to make them, they’re really easy) DEFINITELY READ THIS, 794 tells you premade c++ functions that you can use with this DEFINITELY LOOK AT THIS because it’ll make your life easier. A complete list of functions that you can use with your cstring are http://www.cplusplus.com/reference/clibrary/cstring/ This lab gives a nice intro to them too: http://1300.dupland.com/recitation-6. (more on cstrings later) Included in this are 3 files, A header file of all the functions you should implement, a .cpp file that includes the skeleton of all these functions (with a few of them implemented), and a main.cxx file that will allow you to test your program. Here is what the .h file looks like: *** #ifndef BIGINT_H #define BIGINT_H #include
