Thursday, October 4, 2012

Big Integer Implementation (C++)

Been a while, but I finally have things to post!

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.

Friday, May 4, 2012

Introduction

Hey everyone, my name is Chad Campbell and I am currently a 3rd year Computer Science student at Rochester Institute of Technology. Nice to meet you! :)

I'm creating this blog as an effort to both record my experiences and expand my portfolio. I will be documenting my school projects, my programming learnings and a new personal project I have taken on to create a game from scratch using SDL inside the C++ language.

I will try to keep this updated as possible and provide you with some nice (or bad) code examples along my journey for both feedback and teaching material for inexperienced programmers. Feel free to comment on any of my posts with any feedback you'd like to leave.

Happy May the 4th!

Chad