#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//utility funcs whose names are self-explaining
int toInt(char c) { return c - '0'; }
char toChar(int i) { return i + '0'; }
//multiply s by a, s is a long string, a is a single digit, and move the result offset position to the left
char *mul(const char *s, char a, int offset) {
int l = (int)strlen(s);
char *r = (char*)malloc((l + 1) * sizeof(*r));
for (int i = 0; i < l + 1; i++) { *(r + i) = '0'; }
int ai = toInt(a);
for (int i = l - 1; i >= 0; i--) {
int cr = toInt(*(s + i)) * ai + toInt(*(r + i + 1));
*(r + i + 1) = toChar(cr % 10);
*(r + i) = toChar(cr / 10);
}
int cpyl = *r == '0' ? l : l + 1;
char *ret = (char*)malloc(sizeof(*ret) * (cpyl + offset));
strcpy(ret, r + (*r == '0' ? 1 : 0));
for (int i = cpyl; i < cpyl + offset; i++) { *(ret + i) = '0'; }
return ret;
}
//return a string by appending leading zeros to s so that it is of length l
char *normalize(const char *s, int l) {
int sl = (int)strlen(s);
char *r = (char*)malloc(strlen(s) + 1);
strcpy(r + l - sl, s);
for (int i = 0; i < l - sl; i++) { *(r + i) = '0'; }
return r;
}
//cut leading zeros
char *cut(const char *s) {
int i = 0;
while (toInt(*(s + i++)) != 0);
char *ret = (char*)malloc(strlen(s) - i + 1);
strcpy(ret, s + i);
return ret;
}
//there should be enouth space in a to hold the result
void add(char *a, const char *b) {
int bl = strlen(b);
int al = strlen(a);
char *nb = normalize(b, al);
int carr = 0, r;
for (int i = al - 1; i >= 0; i--) {
r = toInt(*(a + i)) + toInt(*(nb + i)) + carr;
*(a + i) = toChar(r % 10);
carr = r / 10;
}
*a = toChar(carr + toInt(*a));
}
//main drives the calculation
int main(int argc, char *argv[]) {
char *s = argv[1];
char *t = argv[2];
int sl = strlen(s);
int tl = strlen(t);
char *r = (char*)malloc((sl + tl) * sizeof(*r));
for (int i = 0; i < sl + tl; i++) { *(r + i) = toChar(0); }
for (int i = tl - 1; i >= 0; i--) { add(r, mul(s, t[i], tl - 1 - i)); }
printf("%s * %s = %s\n", s, t, cut(r));
free(r);
return 0;
}
网友评论