# Thread: Doing multiplication using numbers in arrays

1. ## 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;
}
}
}```

2. here's an (untested) idea for you. Too hard to explain in words. Assumes you have += overloaded for hugeInt class.
Code:
```int t;
for (t=0; t<hugeSize; t++)
numList[t]=0;
int val;
hugeInt temp;

for (int i=0; i<hugeSize; i++)
{
for(t = 0; t < hugeSize; t++)
temp[t] = 0;
for (int j=0; j<hugeSize; j++)
{
val = n.numList[i] * m.numList[j];
temp[i+j] += val % 10;
temp[i+j+1] += val / 10;
}
numList += temp;
}```

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

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

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

5. Alright, I've worked through some simple examples with my version---see below.
Code:
```for(i = 0; i < hugeSize; i++)
{
for(t = 0; t < hugesize; t++)
temp[t] = 0;
for (int j=0; j<hugeSize; j++)
{
val = n.numList[i] * m.numList[j];
temp[i+j] += val % 10;
temp[i+j+1] += val / 10;
}
numList += temp;
}```
and here's my work through of several simple examples.

let:
n = 7;
m = 9;
i = 0, j = 0
val = 7 * 9 = 63
temp[0] = 0 + 3 = 3
temp[1] = 0 + 6 = 6
now numlist = numlist + temp = 00 + 36
or
numlist[0] = numlist[0] + temp[0] = 0 + 3 = 3
numlist[1] = numlist[1] + temp[1] = 0 + 3 = 6
or 7 * 9 = 63 which is correct
__________________________________________________ _
let:
n = 7
m = 99
i = 0; j = 0
val = 7 * 9 = 63
temp[0] = 0 + 3 = 3
temp[1] = 0 + 6 = 6
i = 0, j = 1
val = 7 * 9 = 63
temp[1] = 6 + 3 = 9
temp[2] = 0 + 6 = 6
now numlist = numlist + temp = 000 + 396
or
numlist[0] = numlist[0] + temp[0] = 3 + 0 = 3
numlist[1] = numlist[1] + temp[1] = 6 + 3 = 9
numlist[2] = numlist[2] + temp[2] = 0 + 6 = 6
or 7 * 99 = 693 which is correct
__________________________________________________ _____
let:
n = 77
m = 99
i = 0; j = 0
val = 7 * 9 = 63
temp[0] = 0 + 3 = 3
temp[1] = 0 + 6 = 6
i = 0, j = 1
val = 7 * 9 = 63
temp[1] = 6 + 3 = 9
temp[2] = 0 + 6 = 6
numlist = numlist + temp = 000 + 396
or:
numlist[0] = numlist[0] + temp[0] = 3 + 0 = 3
numlist[1] = numlist[1] + temp[1] = 6 + 3 = 9
numlist[2] = numlist[2] + temp[2] = 0 + 6 = 6
clear temp to all zero's
numlist remains as is
i = 1; j = 0
val = 7 * 9 = 63
temp[1] = 0 + 3 = 3;
temp[2] = 0 + 6 = 6;
i = 1, j = 1
val = 7 * 9 = 63
temp[2] = 6 + 3 = 9;
temp[3] = 0 + 6 = 6;
numlist = numlist + temp = 396 + 0396;
or
numlist[0] = numlist[0] + temp[0] = 3 + 0 = 3
numlist[1] = numlist[1] + temp[1] = 9 + 3 = 12
numlist[1] = 2 and carry 1 to numlist[2];
numlist[2] = numlist[2] + temp[2] + 1 = 6 + 9 + 1 = 17;
numlist[2] = 7 and carry 1 to numlist[3]
numlist[3] = numlist[3] + temp[3] + 1 = 0 + 6 + 1 = 7
or
numlist[0] = 3;
numlist[1] = 2;
numlist[2] = 7;
numlist[3] = 7;
or 77 * 99 = 7723 which is correct

This algorhithm attemps to mimic long multiplication with temp being a line under the uderscore, in reverse of course.
77
* 99
____
693
6930
_____
7723

Alright, I've worked through some simple examples with my version---see below.
Code:
`  numList += temp;`
and here's my work through of several simple examples.

let:
n = 7;
m = 9;
i = 0, j = 0
val = 7 * 9 = 63
temp[0] = 0 + 3 = 3
temp[1] = 0 + 6 = 6
now numlist = numlist + temp = 00 + 36
or
numlist[0] = numlist[0] + temp[0] = 0 + 3 = 3
numlist[1] = numlist[1] + temp[1] = 0 + 3 = 6
or 7 * 9 = 63 which is correct

now numlist = numlist + temp = 00 + 36
Huh?????

Have you actually compiled and executed a program?

What is numlist? What is temp?

Show me an entire executable snippet that includes data definitions.

Regards,

Dave

7. Dave Evans--No I have not created an executable program. And no I can't gaurantee my algorhithm or code sample will work. But if I can't get an algorhithm to work on paper, then I won't even try to get it to compile. And since it's not my project, I'm just trying to help Neandrake find a way to finish the task.

If you go back to Neandrake's original post, Neandrake appears to be attempting to implement a hugeInt class. He/she provides enough information to work out the schematics of the class, even if he/she didn't post it all. Furthermore, Neandrake posted the version of code that they couldn't get to work.

I found it difficult to explain using words what I thought was wrong with the algorhithm Neandrake posted to multiply two hugeInts together. Therefore I posted an algorhithm of my own. I had worked through my algorhithm on paper before posting so when Neandrake posted that it didn't work I reworked some examples again, and posted them. I thought my paperwork was commented well enough for Neandrake to work through, but then again, who knows. I'll edit my last post to make it even clearer so you can try to walk through it if you want.

Undoubtedly there are other algorhithms to successfully multiply two hugeInts. If you can help assist Neandrake to successful completion using Neandrake's algorhithm, so be it.

8. Code:
`val = n.numList[i] * m.numList[j];`
Assuming 32bit integers, this can easily overflow.
To overflow "n operator m" you need the result to be 2^32 or greater. In an adition to prevent this the arithemic median of the two numbers must be no greater than 2^32/2, or 2^31, but when multipling you need then the median to be 2^32^0.5 or 2^16.
Therefore using integer division and remainder will work for adition, but will easily fail when multiplying.

So to manipulate multiplication you have to separate each of your 32bit int in 16bit pieces and multiply then alone, then add them together.
Adition overflows at max by one unit, multiplication may overflow to 2^32-2 (using again 32bit ints).

9. 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;
}
}
}```

10. Originally Posted by xErath
Code:
`val = n.numList[i] * m.numList[j];`
Assuming 32bit integers, this can easily overflow.
To overflow "n operator m" you need the result to be 2^32 or greater. In an adition to prevent this the arithemic median of the two numbers must be no greater than 2^32/2, or 2^31, but when multipling you need then the median to be 2^32^0.5 or 2^16.
Therefore using integer division and remainder will work for adition, but will easily fail when multiplying.

So to manipulate multiplication you have to separate each of your 32bit int in 16bit pieces and multiply then alone, then add them together.
Adition overflows at max by one unit, multiplication may overflow to 2^32-2 (using again 32bit ints).
He is multiplying decimal digits at a time: n.numList[i] has a value from 0 to 9; m.numList[i] has a value from 0 to 9.

Regards,

Dave

11. 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.

12. 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);
}```

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

Dave Evans--No I have not created an executable program. And no I can't gaurantee my algorhithm or code sample will work.
I'm sorry if I sounded rude. I don't really mean to be that way. I just got caught up in the dilemma of trying to help by giving general advice that might lead to something that works without actually doing the whole job. I think that's the problem a lot of us have. Just trying to help.

Regards,

Dave

14. Originally Posted by xErath
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.
I realize this problem, but at the moment I'm not concerned with it. Originally I had the class using an array of char's to hold the large number, but it got too messy and didn't work a whole lot. I switched over to using ints and have been more succesful with it. Efficiency isn't something I need to worry about at this time. Thanks though.

15. 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.