In my recent endeavors to become more... intimately... familiar with the C++ programming language, I have taken to attempting Project Euler!
These are some fairly thought-provoking mathematical challenges that can be solved using the power of COMPUTERS! And they are especially handy in learning or practicing your programming language of choice.
As I was moving from challenge to challenge, most of them are straight-forward after a little thought. However, the first one that provided me with a challenge (and inspiration) was a little something they call Challenge #16.
Challenge: What is the sum of the digits of the number 21000?
At first you think, man this is pretty easy! C++ has a nice little function named pow in math.h! This is what I thought as well, but lo and behold 2 to the thousandth power is a fairly large number! In fact it's approximately:
1.071509e+301
Which is exactly what the output of pow( 2.0, 1000 ) will give you, unfortunately we need all the digits and, as my hour or two messing with the precision of pow told me, you just can't get it from this.
So I am brought to the topic of this post, my own personal implementation of BigInteger. The goal of my BigInteger is meant to store an int only limited by the capacity of your imagination! (and computer memory) As this is something semi crude that I have done in a few hours, it is neither that pretty nor complete, but it by golly it works!
The first issue that I ran into was choosing the appropriate structure to store this amazingly long integer, and I settled on a string. I may go back and use vectors but I have a bad feeling it would negatively impact performance as inserting at the front of a vector is extremely inefficient and I would rather concatenate strings.
So my basic concept is I want each character to represent a digit in the number, and perform normal operations appropriately. (+, *, ^)
The main thing you have to understand is that raising a number to a power is multiplying it times itself that many times. For example, 2 ^ 4 would just be 2 multiplied four times!
2^4 = 2 * 2 * 2 * 2
The same goes for multiplication simplified to addition
2*4 = 2 + 2 + 2 + 2
You might be saying that you already understand basic math, however these concepts are important as we design our operator functions.
x ^ y calls (x * x )(y times) and i * j calls (i + i) (j times)
So my functions look a little like ** Please note this is extremely pseudo-pseudocode **
// Return the sum of this number and the other number
operator+(BigInt other){ return this + other: }
// Add this number to result, however many times other says to.
operator*(BigInt other) {
int result = 0;
do(other-num-of-times)
{ result += this; }
return result;
}
//Multiply the result by this, however many times other says to.
operator^(BigInt other) {
int result = 1;
do(other-num-of-times)
{ result *= this; }
return result;
}
You can see how these methods cascade into each other. I chose to do it iteratively because that is what came to mind first and is easily readable.
Well that's I all can I get down for right now, I'll detail my approach to actually adding the two numbers in the next post. And in either that one or the next I will go over overloading operator<< and how the friend keyword works so we can get some custom output for our class.
