воскресенье, 20 апреля 2014 г.

Multiplication of big numbers represented as strings

This is the usual task in interview: solve multiplication of integer numbers presented as strings, for ex., "25" * "25" = "625". Length of these strings may be any (not 16 bits or 32 bits only).
Implementation will use school way of multiplication of numbers (sign is ignored), see:
   1856
   1856
   ----
  11136
  9280
14848
1856
=======
3444736
So, "1856" * "1856" = "3444736", we multiply each digit of second number on each digit of first one, shift result number by one to left, summarize them and don't forget about carry. Carry is of 2 kinds: carry of multiplication and carry of sum. Algorithm is:
  • multiply last digit of 2nd number by last digit of 1st one
  • write result (only low digit) in result string at LAST POSITION
  • if resulting number is > 10, save carry (divided by 10)
  • make the same with the 2nd digit of 2nd number, but instead of saving resulting digit, make summation: with carry of multiplication AND carry of sum
  • don't forget to make shifting to left when go to next digit of 1nd number
So, each "saving" of result digit should make summation and there are not number 9280 in middle result but sum of 11136 and 9280 ("103936"). Implementation on C looks like this:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "algutils.h"

#define ASCII2I(CH) ((CH)?((CH)-'0'):0)
#define I2ASCII(I) ((I)+'0')

char* mul(const char *s1, const char *s2, char *res, int reslen)
{
    int r, // index in result string
        i, // index in s1
        _i, // offset (to left) of next middle number
        j, // index in s2
        len1 = strlen(s1), len2 = strlen(s2);
    int d1, // digit in s1
        d2, // digit in s2
        ts, // temporary summ
        c, // curry in multiplication
        cs; // curry in summation
    memset(res, 0, reslen);
    for (i=len2-1, _i=0, cs=0; i>=0; i--, _i++) {
        d2 = ASCII2I(s2[i]);
        r = reslen - 2 - _i;
        for (j=len1-1, c=0; j>=0; j--) {
            d1 = ASCII2I(s1[j]);
            d1 = d1*d2 + c;
            ts = ASCII2I(res[r]) + (d1%10) + cs;
            res[r] = I2ASCII(ts%10);
            cs = ts/10;
            c = d1/10;
            r--;
        }
        do {
            // do rest of sum (high digits)
            ts = ASCII2I(res[r]) + (c%10) + cs;
            if (!ts) break;
            res[r] = I2ASCII(ts%10);
            cs = ts/10;
            r--;
        } while (cs);
    }
    return (res + r + 1);
}

///////////////////////////////////////////////
//              Main: tests
///////////////////////////////////////////////

#define RND(N) (srand(time(NULL)), rand()%(N))

int main(void)
{
    char _res[32], *res;
    char s1[32] = {0};
    char s2[32] = {0};
    int n1, n2, rn, resn, chk;

    //printf("%s\n", mul("1856", "1856", _res, sizeofarray(_res)));
    //return 0;

    for (int i=0; i<100; i++) {
        sprintf(s1, "%d", RND(9999999));
        sprintf(s2, "%d", 1+RND(9999999));
        printf("STR: %s * %s = %s\n", s1, s2, (res=mul(s1, s2, _res, sizeofarray(_res))));
        n1 = atoi(s1); n2 = atoi(s2); rn = n1*n2; resn = atoi(res);
        printf("CTR: %d * %d = %d\n", n1, n2, rn);
        printf("verify <%d>: %d (%d ? %d)\n", i, (chk=(resn==rn)), rn, resn);
        if (!chk) { printf("FAILED!\n"); return (1); }
        else printf("\n\n");
    }
    printf("All tests are passed\n");
    return (0);
}
Tests are cycle of multiplication of random numbers. If test is failed, cycle is break.

Комментариев нет:

Отправить комментарий

Thanks for your posting!