int array multiplication

[sternhagenr]

does anybody know a way to multiply two int arrays together as if they were two large numbers?

I cannot use the big integer class for this

[Fubarable]

I hear a voice whispering "for loop" in my ear. What have you tried, and what happened when you tried it?

[JeffGrigg]

Suppose you wrote a five digit number on a piece of paper, like say 27972. Suppose you wrote another five digit number underneath it -- say 98374. Now if you only know how to multiply a one digit number by another one digit number (to get a possibly two digit result), do you suppose that you could multiply those two numbers, using pencil and paper, and get the correct result?

If you can do that, then you can probably figure out how to multiply arrays of int values -- kind of like how the BigInteger class does it.

[sternhagenr]

I know I will need a for loop, my first thought would be a nested for loop were one element of one array was multiplied by all elements of the other,this would work if not for the carrying over of the numbers and the extra addition that comes with multiplying multi-digit numbers

[sternhagenr]

perhaps something like this but accounting for carry overs and zeroes

for(int i=0;i<sizeofarray1;i++)
{
for(int j=0;j<sizeofarray2;j++)
{
product=product+(array1[i]*array2[j]);
}

}

I was also thinking of haveing a variable that provided the product of two digits is greater than 10 gets added to the next product, however this still does not help with all the carry over concerns, for instance when you do this by hand you put zeroes depending on which digit is being multiplied.

I also have to have the product be an array or else I risk overflow

here is what I have tried which did not work

int [] multiply(int array1[],int array2[])
{
int[] product=new int[2*size];

int carryover=0;

for(int i=0;i<size;i++)
{
for(int j=0;j<othersize;j++)
{
product[i]=(array1[i]*array2[j])+carryover;
if(product[i]>10)
{
carryover=product[i]/10;
product[i]=product[i]/(carryover*10);
}
}

}

return product;

}


It is pretty hard to wrap my head around this stuff, so any suggestions would be appreciated

[Willriker]

I am not understanding the definition of the problem. Are you trying to do something similar to multiplying matrices, like this?

Matrix Multiplication: How to Multiply Two Matrices Together

if so, two for loops, one inside of the other should be ok for a two 2d arrays, no?

[sternhagenr]

no, just trying to multiply two 1 dimensional int arrays together treating them as if they are single large numbers

[JeffGrigg]

It can help to go step by step through an example like How to Do Long Multiplication - wikiHow and see how it corresponds to your code. I'd say that 'array1' is the second line of digits, and that 'i' counts from right to left. And the 'product' array is the very last line -- value = 24192 in the example at the link above.

So the 'product' array is twice the size of the other two arrays, but it's indexed using 'i', which is limited to half that size. This doesn't seem right.

I see one major problem with how 'carryover' is handled, and one or two more subtle problem(s).

P.S. Other than those issues, it looks pretty good. ;->

[sternhagenr]

thanks, I will try that

[Norm]

arrays together treating them as if they are single large numbers

How does that work?
If I have an array: {2,3,4} and multiplty that by another array: {7,8} what would results be?
There are many ways to look at this:
234*78
2+3+4*7+8
2*7 + 2*8 + 3*7 + 3*8 + 4*7 + 4*8
etc
What would you want the answer to be for the above two arrays?

[JeffGrigg]

How does that work?
If I have an array: {2,3,4} and multiplty that by another array: {7,8} what would results be?
...
What would you want the answer to be for the above two arrays?

An excellent question, of course.

What sternhagenr's code seems to be doing is most like "87 * 432 = ?"

Putting some thought into what is wanted could be wise.