Thread: Doing multiplication using numbers in arrays

Is he? Then neandrake let me note that you class for the time being is terribly unifficient. But you'll work on it.
But why using a int to store something smaller that half char?? 32bit register manipulations are faster?? Yeap maybe, but then that's a waste of memory.

Neandrake: I still can't explain what's happening in a general sense using just english, so I wrote a program using a simple HugeInt class. The limitation of the class is as you've described: the HugeInt(long) constructor won't hold as many ints as I'd like. I suspect you will want to accept input as a string and convert the char to ints before storing them in numlist eventually. But getting the algorhithm down first in a manner you can grasp is important.

Code:

#include <iostream>
using namespace std;

const int MAX = 20;

struct HugeInt
{
  int numlist[MAX];
  HugeInt();
  HugeInt(long);
  HugeInt(const HugeInt &);
  HugeInt & operator=(const HugeInt &);
  friend ostream & operator <<(ostream & os, const HugeInt &);
  HugeInt operator+(const HugeInt &);
  friend HugeInt operator*(const HugeInt &, const HugeInt &);
};

HugeInt::HugeInt()
{
  int i;
  for(i = 0; i < MAX; ++i)
	numlist[i] = 0;
}

HugeInt::HugeInt(long num)
{
  int i = 0;
  for(i = 0; i < MAX; ++i)
	numlist[i] = 0;

  i = 0;
  while(num > 0 && i < MAX)
  {
	numlist[i++] = num % 10;
	num /= 10;
  }
}

HugeInt::HugeInt(const HugeInt & h)
{
  int i;
  for(i = 0; i < MAX; ++i)
	numlist[i] = h.numlist[i];
}

HugeInt & HugeInt::operator=(const HugeInt & rhs)
{
  int i;
  for(i = 0; i < MAX; ++i)
	numlist[i] = rhs.numlist[i];
  return *this;
}

ostream & operator<<(ostream & os, const HugeInt & h)
{
  int i;
  bool primed = false;
  for(i = MAX - 1; i >= 0; --i)
  {
	if(h.numlist[i] != 0 && !primed)
	  primed = true;
	if(primed)
	  os << h.numlist[i];
  }
  return os;
}

HugeInt HugeInt::operator+(const HugeInt & rhs)
{
  HugeInt r;

  int i;
  for(i = 0; i < MAX; ++i)
  {
	 r.numlist[i] = r.numlist[i] + numlist[i] + rhs.numlist[i];
	 if(r.numlist[i] > 9)
	 {
	   r.numlist[i] = r.numlist[i] % 10;
	   r.numlist[i + 1] = r.numlist[i + 1] + 1;   
	 }
  }
  return r;
}

HugeInt operator *(const HugeInt & n, const HugeInt & m)
{
  HugeInt r;
  HugeInt temp;
  int i, j, t, val;
  
  for(i = 0; i < MAX; ++i)
  {
	for(j = 0; j < MAX; ++j)
	{
	  val = n.numlist[i] * m.numlist[j];
	  temp.numlist[i + j] += val % 10;
	  temp.numlist[i + j + 1] += val/10;
	}

	r = r + temp;

	for(t = 0; t < MAX; ++t)
	  temp.numlist[t] = 0; 
  }
  return r;
}

int main()
{
  HugeInt a(99999);
  HugeInt b(99999);
  HugeInt c;
  c = a * b;
  cout << c << endl;
  return 0;
}

I'll have to try Dave Evans' shortened schema.

Originally Posted by elad

Neandrake: I still can't explain what's happening in a general sense using just english, so I wrote a program using a simple HugeInt class.

I'll have to try Dave Evans' shortened schema.

elad: see my corrected code.

I really like your work, and it shows the power of C++ (using the overloaded + to add in each partial sum). Much more elegant than the old-fashioned C-language approach.

One very minor point: For your overloaded << operator, if the HugeInt has a value of zero, nothing gets printed. Maybe something like this would be appropriate?

Code:

  for(i = MAX - 1; i >= 1; --i)
  {
	if(h.numlist[i] != 0 && !primed)
	  primed = true;
	if(primed)
	  os << h.numlist[i];
  }
  os << h.numlist[0];

Regards,
Dave

Drat. Good point about the value being zero business. I overlooked that in my effort to ignore leading zeros. Special case time.