Implementation will use school way of multiplication of numbers (sign is ignored), see:
1856 1856 ---- 11136 9280 14848 1856 ======= 3444736So, "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
#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!