multiply two arrays with int values

Question

suppose I have n1 and n2 I want to multiply them for example I have array

n1={1,2,3};

and in

n2={5,6}   

they are two integers in n1 we have the 123 and in n2 56

123*56=6888

then in result I should have

result = {6,8,8,8}    

here is the incomplete algorithm which I thought

for(i in n1 bigger array)
    for(j in n2 smaller one)
    {
        mult=n1[i]*n2[j]
        mult+= carry;

        if(mult>=10)
        {
            carry = (mult/10);
            mult-= (carry*10);
        }
    }
}

How can I write it? I don't know the place of store after finishing the insider loop I should store num in array and then compute again and... How should I write it? I searched the whole of overflow here but I didn't find about it in c code

The Goal is to Compute the Large numbers Integer Numbers has 8 Bytes,in other words 64 bits so they can store 2pow64-1 which is 19 digits now this will help to compute very larger than 19 digits

Answer 1

It would be slightly easier if your digit-arrays were little-endian. Then your example multiplication would look

 3  2  1 * 6 5
---------------
18 12  6
   15 10  5
---------------
18 27 16  5    // now propagate carries
 8 28 16  5
 8  8 18  5
 8  8  8  6
============

The product of n1[i] and n2[j] would contribute to result[i+j]. The main loop could roughly look like

for (i = 0; i < l1; ++i) // l1 is length of n1
{
    for (j = 0; j < l2; ++j) // l2 is length of n2
    {
        result[i+j] += n1[i]*n2[j];
    }
}
// now carry propagation

You see that the result must be at least (l1-1) + (l2-1) + 1 long, since the product of the most significant digits goes int result[(l1-1) + (l2-1)]. On the other hand, n1 < 10^l1 and n2 < 10^l2, so the product is < 10^(l1+l2) and you need at most l1+l2 digits.
But if you're working with char (signed or unsigned), that will quickly overflow in each digit, since (for k <= min(l1-1,l2-1)) k+1 products of two digits (each can be as large as 81) contribute to digit k of the product.

So it's better to perform the multiplication grouped according to the result digit, accumulating in a larger type, and doing carry propagation on writing the result digit. With little-endian numbers

char *mult(char *n1, size_t l1, char *n2, size_t l2, size_t *rl)
{
    // allocate and zero-initialise, may be one more digit than needed
    char *result = calloc(l1+l2+1,1);
    *rl = l1 + l2;
    size_t k, i, lim = l1+l2-1;
    for (k = 0; k < lim; ++k)
    {
        unsigned long accum = result[k];
        for (i = (k < l2) ? 0 : k-(l2-1); i <= k && i < l1; ++i)
        {
            accum += (n1[i] - '0') * (n2[k-i] - '0');
        }
        result[k] = accum % 10 + '0';
        accum /= 10;
        i = k+1;
        while(accum > 0)
        {
            result[i] += accum % 10;
            accum /= 10;
            ++i;
        }
    }
    if (result[l1+l2-1] == 0)
    {
        *rl -= 1;
        char *real_result = calloc(l1+l2,1);
        for (i = 0; i < l1+l2-1; ++i)
        {
            real_result[i] = result[i];
        }
        free(result);
        return real_result;
    }
    else
    {
        result[l1+l2-1] += '0';
        return result;
    }
}

For big-endian numbers, the indexing has to be modified - you can figure that out yourself, hopefully - but the principle remains the same.

Indeed, the result isn't much different after tracking indices with pencil and paper:

char *mult(char *n1, size_t l1, char *n2, size_t l2, size_t *rl)
{
    // allocate and zero-initialise, may be one more digit than needed
    // we need (l1+l2-1) or (l1+l2) digits for the product and a 0-terminator
    char *result = calloc(l1+l2+1,1);
    *rl = l1 + l2;
    size_t k, i, lim = l1+l2-1;
    // calculate the product from least significant digit to
    // most significant, least significant goes into result[l1+l2-1],
    // the digit result[0] can only be nonzero by carry propagation.
    for (k = lim; k > 0; --k)
    {
        unsigned long accum = result[k]; // start with carry
        for (i = (k < l2) ? 0 : k-l2; i < k && i < l1; ++i)
        {
            accum += (n1[i] - '0') * (n2[k-1-i] - '0');
        }
        result[k] = accum % 10 + '0';
        accum /= 10;
        i = k-1;
        while(accum > 0)
        {
            result[i] += accum % 10;
            accum /= 10;
            --i;
        }
    }
    if (result[0] == 0) // no carry in digit 0, we allocated too much
    {
        *rl -= 1;
        char *real_result = calloc(l1+l2,1);
        for (i = 0; i < l1+l2-1; ++i)
        {
            real_result[i] = result[i+1];
        }
        free(result);
        return real_result;
    }
    else
    {
        result[0] += '0'; // make it an ASCII digit
        return result;
    }
}

Edit: added 0-terminators

Note: these are not NUL-terminated (unsigned) char arrays, so we need to keep length information (that's good to do anyway), hence it would be better to store that info together with the digit array in a struct. Also, as written it only works for positive numbers. Dealing with negative numbers is awkward if you only have raw arrays, so another point for storing additional info.

Keeping the digits as '0' + value doesn't make sense for the computations, it is only convenient for printing, but that only if they were NUL-terminated arrays. You may want to add a slot for the NUL-terminator then. In that case, the parameter rl in which we store the length of the product is not strictly necessary.

Answer 2

Definitely an interesting problem.

Here was my thought:

• For the given array, append each value to the end of a string. Thus you construct a string of the numbers in order. {1,2,3} = "123"
• Then, you use a "ToInteger" method that you can find in one of the C libraries. Now you have your number to multiply with.

With this logic, you can probably look up how the "ToInteger" or "ToString" methods work with numbers, which would lead to an answer.