Thread: Doing multiplication using numbers in arrays

I'm writing a class that can handle integers up to 40 characters long, I have been able to get add and subtract working fine, but I can't see what is wrong with multiply.

numList is an array of integers (i know, they could be smaller in size), and it just holds the number, index 0 being the least significant number. Using this code, I get small negative numbers (I'm assuming because numList is signed, for when I set it as unsigned, the numbers are extremely large). hugeSize is a #define set at 40. Does anyone see what is wrong with my code? (please no code posting unless it's a small mistake). thank you. (ps, if you need more code, or prototypes, I can upload).

Code:

void hugeInt::multiply(hugeInt n, hugeInt m)	//multiply two hugeInts
{
	for (int t=0; t<hugeSize; t++)	//clear current
		numList[t]=0;
	int val=0;
	for (int i=0; i<hugeSize; i++)	//multiply each element in n by
	{									//every element in m
		for (int j=0; j<hugeSize; j++)
		{
			val = n.numList[i] * m.numList[j];
			numList[i+j] = val % 10;
			numList[i+j+1] += val / 10;
			numList[i+j] += val % 10;
		}
	}
}

I tried it and got different wrong numbers. Hrmph, thanks for the input, gonna try fiddling with it tomorrow.

Originally Posted by neandrake

I tried it and got different wrong numbers. Hrmph, thanks for the input, gonna try fiddling with it tomorrow.

Why doesn't your code give the right answer?

Well, have you tried to do something simple, like multiplying 1 by 2? I got 4 with your code.

Look at how you handle the cross products (put cout << inside the loops inside the product() function). What's going on? You tell me.

I see two ways to handle it: Create each cross product and simply add into each partial sum.

Then after all multiplications are done, start with the least significant digit. If it's greater than 9 (digit/10 not equal to 0), increment the "next digit" by "this digit"/10, then replace "this digit" by "this digit"%10.

The other way is to make the correction in place (that is, as each cross product is added into the previous value for that cross product, see if it is greater than 9 and make the correction as I indicated above).


After you get it to multiply 1*2, try 9*9, 99*99, etc. (Remember that, in general, multiplying two n-digit numbers can give a product with as many as 2n digits.)
Regards,

Dave

ok, so I tried rewriting the whole function with no luck still. This is so aggrevating. I've tried following through the code and I can't see why it doesn't work. This was my original function, which makes more sense to me, but it still doesn't work!

Code:

void hugeInt::multiply(hugeInt n, hugeInt m)	//multiply two hugeInts
{
	for (int t=0; t<hugeSize; t++)	//clear current
		numList[t]=0;
	hugeInt temp;
	int mult=0;
	int carry=0;
	for (int i=0; i<hugeSize; i++)
	{
		for (int p=0; p<hugeSize; p++)
			temp.numList[p] = 0;
		for (int j=0; j<hugeSize; j++)
		{
			mult = n.numList[i] * m.numList[j] + carry;
			if (mult > 9)
			{
				carry = mult / 10;
				mult -= carry * 10;
			}
			else
			{
				carry = 0;
			}
			temp.numList[j] = mult;
		}
		add(*this, temp);
	}
}

Originally Posted by neandrake

ok, so I tried rewriting the whole function with no luck still. This is so aggrevating. I've tried following through the code and I can't see why it doesn't work. This was my original function, which makes more sense to me, but it still doesn't work!

At the top of this thread you said that you didn't want anyone to furnish you with detailed code, so up until now I have tried to keep things general. I will now get a little more specific, so if you don't to see some code, stop reading now.

Here's an example in C, using your program as a starting point:

(Yes, I know this is the C++ board, but the algorithm applies to C and C++ users alike --- so sue me.)

Now, just because it works for a few examples doesn't mean that you should accept it as perfect. Test, test, test (but remember that you can't prove a program is correct by testing --- make sure it does exactly what you want.)

Change SIZE to anything you want, and use any numbers you want (Obviously it only works for non-negative integers.)

Code:

#include <stdio.h>
#include <stdlib.h>

void product(int *n, int *m, int size);
#define SIZE 4

int main()
{
  int i;
  int a[SIZE] = {7, 0, 0, 0};
  int b[SIZE] = {9, 9, 0, 0};

  printf("a: ");
  for (i = 0; i < SIZE; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");

  printf("b: ");
  for (i = 0; i < SIZE; i++) {
    printf("%d ", b[i]);
  }
  printf("\n");

  product(a, b, SIZE); /* calculate and print the product */
  
  return 0;
}


void product(int *n, int *m, int size)
{
  int i, j, t;
  int val;

  int *temp;/* will hold the product then disappear */

  temp = malloc(2*size * sizeof(int));
  if (!temp) {
    fprintf(stderr, "Can't allocate storage for temp in product()\n");
    return;
  }

  for(t = 0; t < size; t++) {
        temp[t] = 0;
  }

  for(i = 0; i < size; i++) {
    for (j=0; j < size; j++) { 
          val = n[i] * m[j]; /* partial product */
          temp[i+j]   += val % 10; /* partial sum this digit */
          temp[i+j+1] += val / 10; /* carry into next digit */
    }
  }
  printf("temp: ");
  for (i = 0; i < 2*size; i++) {
    printf("%d ", temp[i]);
  }
  printf("\n");

  free(temp);
}

[edit]
Disclaimer: This is a test case; I have tried to make it correct, but I make no claims as to optimality, efficiency, elegance or anything else. If it helps,, I say, "Good." If not, I say, "Good day."
[/edit]


Regards,

Dave