tag:blogger.com,1999:blog-40600192067492862932024-02-08T08:55:01.359-08:00Null TerminationAnonymoushttp://www.blogger.com/profile/08675483620259764429noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-4060019206749286293.post-50370851357893040232012-10-04T18:27:00.003-07:002012-10-04T18:31:50.605-07:00Big Integer Implementation (C++)Been a while, but I finally have things to post!<br />
<br />
In my recent endeavors to become more... intimately... familiar with the C++ programming language, I have taken to attempting Project Euler!<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://projecteuler.net/images/pe_banner_dark.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="72" src="http://projecteuler.net/images/pe_banner_dark.png" width="400" /></a></div>
<br />
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.<br />
<br />
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 <b>Challenge #16</b>.<br />
<br />
<b style="font-family: 'Trebuchet MS', sans-serif; font-size: 18px; text-decoration: none;"><span style="color: red;"> Challenge: What is the sum of the digits of the number 2<sup>1000</sup>?</span></b><br />
<b style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px; text-decoration: none;"><br /></b>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">At first you think, man this is pretty easy! C++ has a nice little function named <b><span style="color: orange;">pow</span></b> in <b><span style="color: orange;">math.h</span></b>! 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:</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span><b style="font-family: 'Trebuchet MS', sans-serif; font-size: 20px; text-decoration: none;"> 1.071509e+301</b><br />
<br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">Which is exactly what the output of <b><span style="color: orange;">pow( 2.0, 1000 )</span></b> 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.</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">So I am brought to the topic of this post, my own personal implementation of <b><span style="color: orange;">BigInteger</span></b>. 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!</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">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.</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">So my basic concept is I want each character to represent a digit in the number, and perform normal operations appropriately. (+, *, ^)</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">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!</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"> 2^4 = 2 * 2 * 2 * 2</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">The same goes for multiplication simplified to addition</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"> 2*4 = 2 + 2 + 2 + 2</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">You might be saying that you already understand basic math, however these concepts are important as we design our operator functions.</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">x ^ y calls (x * x )(y times) and i * j calls (i + i) (j times)</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;">So my functions look a little like ** Please note this is extremely pseudo-pseudocode **</span></span><br />
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><br /></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="color: #f6b26b; font-size: 14px;"><i>// Return the sum of this number and the other number</i></span></span><br />
<span style="color: orange; font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><i>operator+(BigInt other){ return this + other: } </i></span></span><br />
<span style="color: orange; font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><i><br /></i></span></span>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="color: #f6b26b; font-size: 14px;">// Add this number to result, however many times other says to.</span></span><br />
<span style="color: orange; font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><i>operator*(BigInt other) { </i></span></span><br />
<span style="color: orange; font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><i> int result = 0;</i></span></span><br />
<span style="color: orange; font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"><i> do(other-num-of-times) </i></span></span><br />
<i><span style="color: orange;"><span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 14px;"> {</span></span><span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"> result += this; }</span></span></i><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;"> return result;</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;">}</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;"><br /></span></i></span>
<span style="color: #f6b26b; font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i>//Multiply the result by this, however many times other says to.</i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;">operator^(BigInt other) {</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;"> int result = 1;</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;"> do(other-num-of-times)</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;"> { result *= this; }</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;"> return result;</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><i><span style="color: orange;">}</span></i></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><br /></span>
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;">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. </span><br />
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;"><br /></span>
<span style="font-family: 'Trebuchet MS', sans-serif; font-size: 14px;">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<b> <span style="color: orange;">operator<<</span></b> and how the <b><span style="color: orange;">friend keyword</span></b> works so we can get some custom output for our class.</span>Anonymoushttp://www.blogger.com/profile/08675483620259764429noreply@blogger.com0tag:blogger.com,1999:blog-4060019206749286293.post-76524994510719666712012-05-04T10:29:00.001-07:002012-05-04T10:29:07.958-07:00IntroductionHey 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! :)<br />
<br />
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.<br />
<br />
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.<br />
<br />
Happy May the 4th!<br />
<br />
ChadAnonymoushttp://www.blogger.com/profile/08675483620259764429noreply@blogger.com0