Thread: Multiplying Huge numbers in integer arrays

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    3

    Question 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);
    }

  2. #2
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    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!!
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    3
    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);
    }
    Do you specifically have to store these large numbers in base 10?
    Yes

    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.

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    3
    Quote Originally Posted by neandrake View Post
    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 View Post
    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!

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by invierno View Post
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  2. No Match For Operator+ ???????
    By Paul22000 in forum C++ Programming
    Replies: 24
    Last Post: 05-14-2008, 10:53 AM
  3. Finding the sum of even numbers using arrays
    By Fox101 in forum C Programming
    Replies: 7
    Last Post: 12-03-2007, 02:20 PM
  4. load gif into program
    By willc0de4food in forum Windows Programming
    Replies: 14
    Last Post: 01-11-2006, 10:43 AM
  5. using arrays to sort numbers
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 10:14 PM