For part of my assignment, we are to write a function that overloads the * operator so that we can multiply 2 list<short int>. We are given the BigInt.h and part of BigInt.cpp (It'd be easier if we didn't have to use this format, I know, but we're supposed to add on to this code).
One thing that makes this a bit complicated is how the BigInt is read in. Instead of each node containing a single integer, it contains a block of 3 integers. This is so that the display() function can format the output with correct commas and such, I guess.
Here is the BigInt.h
#include <iostream>
#include <iomanip>
#include <list>
#ifndef BIGINT
#define BIGINT
const int DIGITS_PER_BLOCK = 3;
class BigInt
{
public:
/***** Constructor *****/
// Let the list<short int> constructor take care of this.
void read(istream & in);
void display(ostream & out) const;
BigInt operator+(BigInt addend2);
BigInt operator*(BigInt multiple2);
private:
list<short int> myList;
};
//------ Input and output operators
inline istream & operator>>(istream & in, BigInt & number)
{
number.read(in);
return in;
}
inline ostream & operator<<(ostream & out, const BigInt & number)
{
number.display(out);
return out;
}
#endifAnd here is the BigInt.cpp
#include <iostream>
#include <cmath>
using namespace std;
#include "BigInt.h"
//--- Definition of read()
void BigInt::read(istream & in)
{
static bool instruct = true;
if (instruct)
{
cout << "Enter " << DIGITS_PER_BLOCK << "-digit blocks, separated by "
"spaces.\nEnter a negative integer in last block to signal "
"the end of input.\n\n";
instruct = false;
}
short int block;
const short int MAX_BLOCK = (short) pow(10.0, DIGITS_PER_BLOCK) - 1;
for (;;)
{
in >> block;
if (block < 0) return;
if (block > MAX_BLOCK)
cerr << "Illegal block -- " << block << " -- ignoring\n";
else
myList.push_back(block);
}
}
//--- Definition of display()
void BigInt::display(ostream & out) const
{
int blockCount = 0;
const int BLOCKS_PER_LINE = 20; // number of blocks to display per line
for (list<short int>::const_iterator it = myList.begin(); ; )
{
out << setfill('0');
if (blockCount == 0)
out << setfill(' ');
if (it == myList.end())
return;
out << setw(3) << *it;
blockCount++ ;
it++;
if (it != myList.end())
{
out << ',';
if (blockCount > 0 && blockCount % BLOCKS_PER_LINE == 0)
out << endl;
}
}
}
//--- Definition of operator+()
BigInt BigInt::operator+(BigInt addend2)
{
BigInt sum;
short int first, // a block of 1st addend (this object)
second, // a block of 2nd addend (addend2)
result, // a block in their sum
carry = 0; // the carry in adding two blocks
list<short int>::reverse_iterator // to iterate right to left
it1 = myList.rbegin(), // through 1st list, and
it2 = addend2.myList.rbegin(); // through 2nd list
while (it1 != myList.rend() || it2 != addend2.myList.rend())
{
if (it1 != myList.rend())
{
first = *it1;
it1++ ;
}
else
first = 0;
if (it2 != addend2.myList.rend())
{
second = *it2;
it2++ ;
}
else
second = 0;
short int temp = first + second + carry;
result = temp % 1000;
carry = temp / 1000;
sum.myList.push_front(result);
}
if (carry > 0)
sum.myList.push_front(carry);
return sum;
}
BigInt BigInt::operator*(BigInt multiple2)
{
BigInt sumOfProducts;
short int first, // a block of 1st multiple (this object)
second, // a block of 2nd multiple (multiple2)
result, // a block in their product
carry = 0; // the carry in multiplying two blocks
int count = 0;
list<short int>::reverse_iterator // to iterate right to left
it1 = myList.rbegin(), // through 1st list, and
it2 = multiple2.myList.rbegin();// through 2nd list
for (it2; it2 != multiple2.myList.rend();++it2)
{
BigInt product;
second = *it2;
while (it1 != myList.rend()) // multiply value of second to entire 1st multiple list
{
first = *it1;
it1++;
int temp = first * second + carry;
result = temp % 1000;
carry = temp / 1000;
product.myList.push_front(result);
}
count++;
if (carry > 0)
product.myList.push_front(carry);
for (int j = 1; j < count; j++) // Take care of adding 0's at the end when second is not in unit's place
product.myList.push_back(0);
if (count == 1) // After first multiplication, set the sum of products to the first obtained product
sumOfProducts = product;
else // Adding the products together to get total product
sumOfProducts = sumOfProducts + product;
}
return sumOfProducts;
}Again, everything but the multiplication function was provided, so we are not allowed to alter that code.
The way I'm trying to tackle this problem is as follows: Suppose you have 1,234 * 5,678. Since nodes are broken into blocks of 3, you would first do 678 * 1,234, then 5,000 * 1,234. However, the problem I'm having is that if I tried to perform this particular example, the 5,000 * 1,234 operation is not occurring.
After many hours of analyzing my code, I believe the problem has to do with the conditions of my main for loop
for (it2; it2 != multiple2.myList.rend();++it2)If we go back to my example (1234*5678), what's happening is that it does do the 678*1234 operation, but once it2 gets incremented, it won't perform the 5000*1234 operation. What I've been trying to do is come up with some alternate condition to put in here that would essentially be something along the lines of
for (it2; it2 != multiple2.myList.rend()[B]+1[/B];++it2)However, anything I've tried in order to simulate this gives me a "List Iterator Not Decrementable" fatal error.
I'm also unsure about the correctness of how I'm trying to handle adding x amount of 0's after a number if I need to (just like I would need to add 3 0's after performing 5*1234 in order to get 5000*1234).