Multiplying up to 20 numbers of 30 digits

Question

I was given a task to multiply up to 20 numbers of 30 digits.I figured out an algorithm to multiply two numbers with 30 digits by going on the digits of both numbers in two loops with quadric complexity. (I think the best way to approach 30 digits is to store the digits of the numbers in an 2D integers array with 20 numbers and each one of them has 30 free slots to fill their digits in these slots) the result will be stored in an array of 30 digits. Now here are my questions and problems:

1. How can I multiply more than 2 numbers of 30 digits at once? which kind of loop should I use? I figured out how to multiply only 2 numbers of 30 digits.

2. getting the numbers in which you want to multiply from the user is another issue like while getting numbers you must know that each one of these numbers has max 30 digits to fill like if I want to get the number 52 from the user I dont to enter 52 and 28 zeros after that like just 52 itself like:

Input: 520000000000000000000000000000 is WRONG

Input: 52 is RIGHT if we didnt enter 28 zeros after 52 itself.

Here is my algorithm to multiply 2 numbers with 30 digits:

for (i = 29; i >= 0; i--)
 {
    for (j = 29, carry_in = 0; j >= 0; j--) 
    {
        n =number_1[i] * number_2[j] + result[i] + carry_in;
        carry_in = n / 10;
        result[i] = (n % 10);
    }
    result[i] += carry_in;
 }

Answer 1

You should implement the Karatsuba algorithm instead. You should write your function as a int* multiply(int* a, int* b), initialize your accumulating variable in main as one of the 20 numbers then loop multiply between your accumulating variable and your remaining 19 numbers.

On a side note, your result is upper-bounded by 600 digits, which is relatively small and Karatsuba will in practice be as fast as all known (FFT-based) multiplication algorithms with better asymptotic time complexity. If you have a very large number (>10^4 digits), I would use Schönhage–Strassen or one of its derivatives such as Fürer.