Multiplying Huge numbers in integer arrays

Hey everybody! I'm new to the forum and I could use some help. I need to write a program that will add and multiply huge numbers up to 30 digits long. I have successfully completed the addition part but I cannot for the life of me get the multiplication to work. I have verified that my code as it stands moves all the digits to the ends of the arrays (ones place f[60] and g[60] with the tens place in f[59] and g[59]) but I cannot get the multiplication and subsequent addition to work.

If you see some extra variables or arrays declared but not used in there, keep in mind I have been trying everything I can think of...

I have verified that this works perfectly up to where the code reads "/*The multiplication algorithm begins here*/," but can someone tell me what the problem is with the multiplication algorithm? Thanks!

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

int main (void)
{
int i=0,k=0;
int tmp1=0, tmp2=0, tmp3=0;
char * a;
a= (char *) malloc(30 * sizeof(char));

char * b;
b= (char *) malloc(30 * sizeof(char));

int * x;
x= (int *) malloc(30 * sizeof(int));

int * y;
y= (int *) malloc(30 * sizeof(int));

int * z;
z= (int *) malloc(61 * sizeof(int));

int * w;
w= (int *) malloc(31 * sizeof(int));

int * v;
v= (int *) malloc(61 * sizeof(int));

int * solution;
solution= (int *) malloc(61 * sizeof(int));


int carry = 0;
int c[61];
int d[61];

int f[61];
int g[61];

printf("\nEnter a number (up to 30 digits in length)> "); scanf("%s", a);

i=0;
while(i < strlen(a)){
c[i] = a[i] - '0';
i++;}
printf("\nThe first number is: ");
for(i=0; i < strlen(a); i++){
printf("%d", c[i]);}
printf("\n");

for(i=0, k = 29; i < strlen(a); i++){
x[k] = c[(strlen(a)-1)-i];
k--;}

printf("\nEnter a second number (up to 30 digits in length)> "); scanf("%s", b);

i=0;
while(i < strlen(b)){
d[i] = b[i] - '0';
i++;}

printf("\nThe second number is: ");
for(i=0; i < strlen(b); i++){
printf("%d", d[i]);}
printf("\n");

for(i=0, k = 29; i < strlen(b); i++){
y[k] = d[(strlen(b)-1)-i];
printf("\nThe sum of the two numbers is: "); for(k=30; k>=0; k--){ w[k] = 0; }

for (k = 29; k >= 0; k--){
w[k] = x[k] + y[k] + w[k];
if (w[k] >= 10){
w[k] = w[k]%10;
w[k-1] = 1;}
}
for(i= -1; i < 30; i++){
printf("%d", w[i]);}
printf("\n");

for(k = 60; k>=0; k--){
z[k] = 0;
f[k] = 0;
g[k] = 0;
solution[k] = 0;
}
for(k = 0; k < 30; k++){
f[k+31] = x[k];
g[k+31] = y[k];
}

printf("\nThe product of the two numbers is: ");

/*The multiplication algorithm begins here*/

for(i= 60; i >= 0; i--) {
for(k=60; k>=0; k--)
{ tmp1 = f[i] * g[k];
z[k] = tmp3 + z[k-1];
tmp3 = tmp1 % 10;
z[k-1]= tmp1 / 10;
}
}

/*The multiplication algorithm ends here*/

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

return(0);
}

So I didn't look through your code, but the basic idea behind implementing addition and subtraction, when both numbers are decimals and represented in arrays, can be implemented the same as you would work it out by hand. Add the 1's column together, and if greater than 10, mod by ten (or just subtract 10), and "carry the 1" to the ten's place. Continue through the array like that. Multiplication can be done similarly. As far as allocating the memory for it, just remember: If you have 2 arrays of numbers which you are adding, the most space the result (in addition) can take up would be 1 more digit than the longest of the two. With multiplication (someone should double-check this, I don't have time to verify), but I believe the longest it could be is the sum of lengths of both numbers (so a 3-digit multiplied by 4 digit would have a max length of 7). Add a few extra on to it for safety and you should be good to go.

On a side note, I've found it easier to store the numbers backwards -- 1's place at index 0, 10's at index 1, etc. Which makes lining up the numbers easier for mathematical purposes (don't have to pad with 0's).

p.s. please use code tags around your code -- this is the biggest reason I skipped over looking at your code.

p.s. again -- Welcome to the board!!

Can you please post code within [code]code goes here[/code] tags mext time so that it preserves the indentation.

Here is the pseudocode for a simple way of doing the multiplication:

Code:

---

result <- 0
do
    if leastSignificantBit of a is set
        result <- result + b
    Shift a right by 1 bit
    Shift b left by 1 bit
repeat until a is zero

---

Note that this first requires writing bitShift functions, but they should be easy as they're just a multiply or divide by two (including the carries again of course). It looks like you already have the add, however you need to make each operation (such as add) into its own function as you will find that you need to build some operations out of other lower level operations.

Do you specifically have to store these large numbers in base 10?
Why are you casting malloc?

Thanks for the welcome! And now I'll do it right:

Code:

---

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

int main (void)
{
int i=0,k=0;
int tmp1=0, tmp2=0, tmp3=0;
char * a;
a= (char *) malloc(30 * sizeof(char));

char * b;
b= (char *) malloc(30 * sizeof(char));

int * x;
x= (int *) malloc(30 * sizeof(int));

int * y;
y= (int *) malloc(30 * sizeof(int));

int * z;
z= (int *) malloc(61 * sizeof(int));

int * w;
w= (int *) malloc(31 * sizeof(int));

int * v;
v= (int *) malloc(61 * sizeof(int));

int * solution;
solution= (int *) malloc(61 * sizeof(int));


int carry = 0;
int c[61];
int d[61];

int f[61];
int g[61];

printf("\nEnter a number (up to 30 digits in length)> "); scanf("%s", a);

i=0;
while(i < strlen(a)){
c[i] = a[i] - '0';
i++;}
printf("\nThe first number is: ");
for(i=0; i < strlen(a); i++){
printf("%d", c[i]);}
printf("\n");

for(i=0, k = 29; i < strlen(a); i++){
x[k] = c[(strlen(a)-1)-i];
k--;}

printf("\nEnter a second number (up to 30 digits in length)> "); scanf("%s", b);

i=0;
while(i < strlen(b)){
d[i] = b[i] - '0';
i++;}

printf("\nThe second number is: ");
for(i=0; i < strlen(b); i++){
printf("%d", d[i]);}
printf("\n");

for(i=0, k = 29; i < strlen(b); i++){
y[k] = d[(strlen(b)-1)-i];
printf("\nThe sum of the two numbers is: ");

for(k=30; k>=0; k--)
{
w[k] = 0;
}

for (k = 29; k >= 0; k--){
w[k] = x[k] + y[k] + w[k];
if (w[k] >= 10){
w[k] = w[k]%10;
w[k-1] = 1;}
}
for(i= -1; i < 30; i++){
printf("%d", w[i]);}
printf("\n");

for(k = 60; k>=0; k--){
z[k] = 0;
f[k] = 0;
g[k] = 0;
solution[k] = 0;
}
for(k = 0; k < 30; k++){
f[k+31] = x[k];
g[k+31] = y[k];
}

printf("\nThe product of the two numbers is: ");

/*The multiplication algorithm begins here*/

for(i= 60; i >= 0; i--) {
for(k=60; k>=0; k--)
{ tmp1 = f[i] * g[k];
z[k] = tmp3 + z[k-1];
tmp3 = tmp1 % 10;
z[k-1]= tmp1 / 10;
}
}

/*The multiplication algorithm ends here*/

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

return(0);
}

---

Quote:

---

Do you specifically have to store these large numbers in base 10?

---

Yes

Quote:

---

Why are you casting malloc

---

Because that's how I was taught :) Seriously, I thought you had to. That was the syntax I learned. Does it store values as integers by default?

Thanks for the pseudocode -- I will review it and try to figure out how to code that.

Quote:

---

Originally Posted by neandrake

With multiplication (someone should double-check this, I don't have time to verify), but I believe the longest it could be is the sum of lengths of both numbers (so a 3-digit multiplied by 4 digit would have a max length of 7). Add a few extra on to it for safety and you should be good to go.

---

You are correct; I looked this up in the preliminary stages of this project.

Quote:

---

Originally Posted by neandrake

On a side note, I've found it easier to store the numbers backwards -- 1's place at index 0, 10's at index 1, etc. Which makes lining up the numbers easier for mathematical purposes (don't have to pad with 0's).

---

I think I worked that out with the padding and all, but thanks!

Quote:

---

Originally Posted by invierno

Because that's how I was taught :) Seriously, I thought you had to. That was the syntax I learned. Does it store values as integers by default?

---

Basically you don't have to cast void* pointers in C because it can be silently converted. The cast can in fact hide a missing #include and cause the program to behave wrongly.
However if you compile the C code as C++ instead then the cast is necessary, except that in C++ you shouldn't really use malloc anyway, you use 'new' and vectors. So basically that amounts to you shouldn't cast it, and there is a commonly referred to entry in the FAQ for this site I believe.
I wouldn't make a big deal of it though. Just know that if I hadn't put in a kind word about it then someone else surely would have brought it up.

You got the code tags sorted, but unfortunately you must have copied the code from the first post where the indentation was already removed. The best way to do it is to make a copy the code you want to paste, replace all tabs with a fixed number of spaces, and then post it here using code tags. :) You are using indentation aren't you?!

I think the very next step, before you start getting the multiplication to work, is to break the code up into functions. You have been taught functions already right?
Make an Add function, then a LeftShift function and a RightShift function, and then make the Multiply function.
If you wanted to, you could even do the LeftShift function by adding the number to itself! Now that's code reuse!