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!