bignum
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int min_(int a, int b) { return a < b ? a : b; }
int max_(int a, int b) { return a > b ? a : b; }
#define BASE 1000000000
typedef struct bignum_t bignum_t;
struct bignum_t {
int size;
int *data;
};
void bignum_print(bignum_t x) {
printf("%d", x.data[x.size - 1]);
for (int i = x.size - 2; i >= 0; --i) {
printf("%09d", x.data[i]);
}
}
bignum_t bignum(int x) {
bignum_t bignum_from_size(int size);
bignum_t ret = bignum_from_size(1);
ret.data[0] = x;
return ret;
}
bignum_t bignum_from_size(int size) {
bignum_t ret = { .size = size };
ret.data = (int *)malloc(size * sizeof(int));
memset(ret.data, 0, size * sizeof(int));
return ret;
}
void bignum_dispose(bignum_t x) { free(x.data); }
bignum_t bignum_resize(bignum_t ret, int size) {
ret.data = realloc(ret.data, size * sizeof(int));
memset(ret.data + ret.size, 0, size * sizeof(int));
ret.size = size;
return ret;
}
bignum_t bignum_add(bignum_t a, bignum_t b) {
bignum_t ret = bignum_from_size(max_(a.size, b.size));
int i, sum, carry = 0, len = min_(a.size, b.size);
for (i = 0; i < len; ++i) {
sum = a.data[i] + b.data[i] + carry;
carry = sum / BASE;
ret.data[i] = sum % BASE;
}
if (ret.size > len) {
int *data = a.size < b.size ? b.data : a.data;
for (; i < ret.size; ++i) {
sum = carry + data[i];
carry = sum / BASE;
ret.data[i] = sum % BASE;
}
}
if (carry) {
ret = bignum_resize(ret, ret.size + 1);
ret.data[i] = carry;
}
return ret;
}
int main() {
bignum_t a = bignum_add(bignum(999999999), bignum(999999999));
// the two temporary bignum(999999999) is not disposed!
bignum_print(a);
bignum_dispose(a);
}
C
INFO