DaniWeb Forum Index > Software Development > C++

C++ RSS

Help - BigInteger Multiplication using STL List

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Mar 2009

Posts: 10

Reputation: DallasEvertts is an unknown quantity at this point

Solved Threads: 0

DallasEvertts DallasEvertts is offline

Offline

Newbie Poster

Help - BigInteger Multiplication using STL List

34 Days Ago

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

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#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;
}
 
#endif
#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;
}

#endif

And here is the BigInt.cpp

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#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;
}
#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

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
for (it2; it2 != multiple2.myList.rend();++it2)
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

Help with Code Tags

(Toggle Plain Text)

for (it2; it2 != multiple2.myList.rend()+1;++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).