Multiplication of very large numbers using character strings

Question

I'm trying to write a C program which performs multiplication of two numbers without directly using the multiplication operator, and it should take into account numbers which are sufficiently large so that even the usual addition of these two numbers cannot be performed by direct addition.

I was motivated for this when I was trying to (and successfully did) write a C program which performs addition using character strings, I did the following:

#include<stdio.h>
#define N 100000
#include<string.h>
void pushelts(char X[], int n){
int i, j;
for (j = 0; j < n; j++){
    for (i = strlen(X); i >= 0; i--){
        X[i + 1] = X[i];
    }
        X[0] = '0'; 
    }
}

int max(int a, int b){
    if (a > b){ return a; }
    return b;
}

void main(){
    char E[N], F[N]; int C[N]; int i, j, a, b, c, d = 0, e;
    printf("Enter the first number: ");
    gets_s(E);
    printf("\nEnter the second number: ");
    gets_s(F);
    a = strlen(E); b = strlen(F); c = max(a, b);
    pushelts(E, c - a); pushelts(F, c - b);
    for (i = c - 1; i >= 0; i--){
        e = d + E[i] + F[i] - 2*'0';
        C[i] = e % 10; d = e / 10;
    }
    printf("\nThe answer is: ");
    for (i = 0; i < c; i++){
        printf("%d", C[i]);
    }
    getchar();
}

It can add any two numbers with "N" digits. Now, how would I use this to perform multiplication of large numbers? First, I wrote a function which performs the multiplication of number, which is to be entered as a string of characters, by a digit n (i.e. 0 <= n <= 9). It's easy to see how such a function is written; I'll call it (*). Now the main purpose is to multiply two numbers (entered as a string of characters) with each other. We might look at the second number with k digits (assuming it's a1a2.....ak) as:

a1a2...ak = a1 x 10^(k - 1) + a2 x 10^(k - 2) + ... + ak-1 x 10 + ak

So the multiplication of the two numbers can be achieved using the solution designed for addition and the function (*).

If the first number is x1x2.....xn and the second one is y1y2....yk, then:

x1x2...xn x y1y2...yk = (x1x2...xn) x y1 x 10^(k-1) + .....

Now the function (*) can multiply (x1x2...xn) with y1 and the multiplication by 10^(k-1) is just adding k-1 zero's next to the number; finally we add all of these k terms with each other to obtain the result. But the difficulty lies in just knowing how many digits each number contains in order to perform the addition each time inside the loop designed for adding them together. I have thought about doing a null array and each time adding to it the obtained result from multiplication of (x1x2....xn) by yi x 10^(i-1), but like I've said I am incapable of precising the required bounds and I don't know how many zeros I should each time add in front of each obtained result in order to add it using the above algorithm to the null array. More difficulty arises when I'll have to do several conversions from char types into int types and conversely. Maybe I'm making this more complicated than it should; I don't know if there's an easier way to do this or if there are tools I'm unaware of. I'm a beginner at programming and I don't know further than the elementary tools.

Does anyone have a solution or an idea or an algorithm to present? Thanks.

Solution 1

There is an algorithm for this which I developed when doing Small Factorials problem on SPOJ.

This algorithm is based on the elementary school multiplication method. In school days we learn multiplication of two numbers by multiplying each digit of the first number with the last digit of the second number. Then multiplying each digit of the first number with second last digit of the second number and so on as follows:

               1234
               x 56
         ------------
               7404
             +6170-   // - is denoting the left shift    
         ------------
              69104  

What actually is happening:

1. num1 = 1234, num2 = 56, left_shift = 0;
2. char_array[] = all digits in num1
3. result_array[]
4. while(num2)
   • n = num2%10
   • num2 /= 10
   • carry = 0, i = left_shift, j = 0
   • while(char_array[j])
     i. partial_result = char_array[j]*n + carry
     ii. partial_result += result_array[i]
     iii. result_array[i++] = partial_result%10
     iv. carry = partial_result/10
   • left_shift++
5. Print the result_array in reverse order.

You should note that the above algorithm work if num1 and num2 do not exceed the range of its data type. If you want more generic program, then you have to read both numbers in char arrays. Logic will be the same. Declare num1 and num2 as char array. See the implementation:

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

int main(void)
{
    char num1[200], num2[200];
    char result_arr[400] = {'\0'};
    int left_shift = 0;

    fgets(num1, 200, stdin);
    fgets(num2, 200, stdin);

    size_t n1 = strlen(num1);
    size_t n2 = strlen(num2);   

    for(size_t i = n2-2; i >= 0; i--)
    {
        int carry = 0, k = left_shift;
        for(size_t j = n1-2; j >= 0; j--)
        {
            int partial_result = (num1[j] - '0')*(num2[i] - '0') + carry;
            if(result_arr[k])
                partial_result += result_arr[k] - '0';
            result_arr[k++] = partial_result%10 + '0';
            carry = partial_result/10;  
        }
        if(carry > 0)
            result_arr[k] = carry +'0'; 
        left_shift++;
    }
    //printf("%s\n", result_arr);

    size_t len = strlen(result_arr);
    for(size_t i = len-1; i >= 0; i-- )
        printf("%c", result_arr[i]);
    printf("\n");   
}

This is not a standard algorithm but I hope this will help.

Solution 2

Bignum arithmetic is hard to implement efficiently. The algorithms are quite hard to understand (and efficient algorithms are better than the naive one you are trying to implement), and you could find several books on them.

I would suggest using an existing Bignum library like GMPLib or use some language providing bignums natively (e.g. Common Lisp with SBCL)

Comments

[Rafael Lerm]

Why character strings and not something like integer arrays?

[Admin]

How can I achieve this given the above circumstances? I want the user to enter two large numbers and I must eventually use indirect addition and multiplication; I'm not seeing how character strings are unnecessary (at least at a few places). Could you please elaborate on what you've said?

[Pascal Cuoq]

In other words, unless you have good reasons to prefer base 10, you would be much, much better off computing using base 2^16 or 2^32 (or 2^64 if your C compiler gives access to the 128-bit result of a 64x64 bit multiplication). Besides, strings representing base-10 numbers waste 246/256 (96%) of the space they occupy.

[Lehs]

Isn't it possible to use BigInt package for this?

[Spektre]

here is mine NTT based Schönhage-Strassen multiplication stackoverflow.com/q/18577076/2521214 with strings multiplication example