美文网首页
Huge Number Multiplication

Huge Number Multiplication

作者: 刘煌旭 | 来源:发表于2020-12-11 13:56 被阅读0次
#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;
}

相关文章

网友评论

      本文标题:Huge Number Multiplication

      本文链接:https://www.haomeiwen.com/subject/uyejgktx.html