/**

array implementation of bignum

**/

#include <stdio.h>

#include <string.h>

#define MAXDG 500

#define PLUS 1

#define MINUS -1

typedef struct {

int sign;

int length;

char dg[MAXDG];

} BN;

int cmp(BN a, BN b);

void sub(BN a, BN b, BN *c);

void add(BN a, BN b, BN *c);

void reverse(BN *c);

void rm_tzeros(BN *c);

void rm_lzeros(BN *c);

void init(BN *a);

int cmp(BN a, BN b) {

if (a.sign == PLUS && b.sign == MINUS) {

return 1;

} else if (a.sign == MINUS && b.sign == PLUS) {

return -1;

} else {

//a and b have same sign

if (a.length > b.length) {

return 1*a.sign;

} else if (a.length < b.length) {

return -1*a.sign;

} else {

//a and b have same sign, same length

int i;

for (i = 0; i < a.length; ++i) {

if (a.dg[i] > b.dg[i]) {

return 1*a.sign;

} else if (a.dg[i] < b.dg[i]) {

return -1*a.sign;

}

}

return 0; //equal

}

}

}

void reverse(BN *c) {

char tmp;

int i;

for (i = 0; i < c->length/2; ++i) {

tmp = c->dg[i];

c->dg[i] = c->dg[c->length-i-1];

c->dg[c->length-i-1] = tmp;

}

}

void rm_lzeros(BN *c) {

int i, j;

for (i = 0; i < c->length; ++i) {

if (c->dg[i] != '0') {

break;

}

}

for (j = 0; i < c->length; ++i, ++j) {

c->dg[j] = c->dg[i];

}

c->length = j == 0?1:j;

c->dg[c->length] = '';

}

void rm_tzeros(BN *c) {

int i, j = 0;

for (i = c->length-1; i > 0; --i) {

if (c->dg[i] == '0') {

j++;

} else {

break;

}

}

c->length -= j;

c->dg[c->length] = '';

}

void sub(BN a, BN b, BN *c) {

int i, j, k;

int borrow = 0;

if (a.sign == MINUS) {

if (b.sign == MINUS) {

sub(b, a, c);

c->sign *= -1;

} else {

b.sign = MINUS;

add(a, b, c);

}

return;

} else {

if (b.sign == MINUS) {

b.sign = PLUS;

add(a, b, c);

return;

}

}

//a.sign == PLUS, b.sign == PLUS

if (cmp(a, b) < 0) {

sub(b, a, c);

c->sign = MINUS;

return;

} else if (cmp(a, b) == 0) {

c->dg[0] = '0';

c->dg[1] = '';

c->length = 1;

c->sign = PLUS;

return;

}

//a.sign == PLUS, b.sign == PLUS, a > b

c->sign = PLUS;

for (i = a.length-1, j = b.length-1, k = 0; i >= 0 && j >= 0; --i, --j, ++k) {

c->dg[k] = a.dg[i] - borrow - b.dg[j];

if (c->dg[k] < 0) {

c->dg[k] += 10;

borrow = 1;

} else {

borrow = 0;

}

c->dg[k] += '0';

}

for (; i >= 0; --i, ++k) {

c->dg[k] = a.dg[i] - borrow;

if (c->dg[k] - '0' < 0) {

c->dg[k] += 10;

borrow = 1;

} else {

borrow = 0;

}

}

c->dg[k] = '';

c->length = k;

//printf("%sn", c->dg);

rm_tzeros(c);

//printf("%sn", c->dg);

reverse(c);

}

void add(BN a, BN b, BN *c) {

int i, j, k;

int carry = 0;

// printf("%d:%dn", a.length, b.length);

if (a.sign == b.sign) {

c->sign = a.sign;

} else {

if (a.sign == MINUS) {

a.sign = PLUS; //tmp

sub(b, a, c);

} else {

b.sign = PLUS; //tmp

sub(a, b, c);

}

return;

}

for (i = a.length-1, j = b.length-1, k = 0; i >= 0 && j >= 0; --i, --j, ++k) {

c->dg[k] = a.dg[i] -'0' + b.dg[j] - '0' + carry;

//printf("%d %d %c %cn",k, c->dg[k], a.dg[i], b.dg[j]);

carry = c->dg[k]/10;

c->dg[k] = c->dg[k]%10 + '0';

// printf("%d %cn", k, (*c->dg[k]);

}

for (; i >= 0; --i, ++k){

if (carry != 0) {

c->dg[k] = carry + a.dg[i] - '0';

carry = c->dg[k]/10;

c->dg[k] = c->dg[k]%10 + '0';

} else {

c->dg[k] = a.dg[i];

}

}

for (; j >= 0; --j, ++k){

if (carry != 0) {

c->dg[k] = carry + b.dg[j] - '0';

carry = c->dg[k]/10;

c->dg[k] = c->dg[k]%10 + '0';

} else {

c->dg[k] = b.dg[j];

}

}

if (carry != 0) {

c->dg[k++] = carry + '0';

}

c->dg[k] = '';

c->length = k;

//printf("%d %sn", c->length, c->dg);

reverse(c);

//printf("%d %sn", c->length, c->dg);

}

void lshift(BN *a, int num) {

int i;

if ((a->length == 1) && (a->dg[0] == '0')) {

return;

}

for (i = 0; i < num; ++i) {

a->dg[i+a->length] = '0';

}

a->length += num;

a->dg[a->length] = '';

}

void mul(BN a, BN b, BN *c) {

int i, j;

init(c);

for (i = a.length - 1; i >= 0; --i) {

for (j = 0; j < a.dg[i]-'0'; ++j) {

//printf("add %s to %sn", b.dg, c->dg);

add(*c, b, c);

}

lshift(&b, 1);

//printf("%s %sn", c->dg, b.dg);

}

c->sign = a.sign*b.sign;

}

void div(BN a, BN b, BN *c) {

int i;

BN tmp;

init(c);

init(&tmp);

for (i = 0; i < a.length; ++i) {

//printf("bf: %sn", tmp.dg);

if (i > 0) {

lshift(&tmp, 1);

} else {

tmp.length = 1;

}

//printf("af: %sn", tmp.dg);

tmp.dg[tmp.length-1] = a.dg[i];

c->dg[i] = '0';

//printf("%d b: %d:%d:%s %d:%d:%sn", i, tmp.sign, tmp.length, tmp.dg, b.sign, b.length, b.dg);

rm_lzeros(&tmp);

while (cmp(tmp, b) >= 0) {

//printf("sub: %s %sn", tmp.dg, b.dg);

sub(tmp, b, &tmp);

c->dg[i]++;

}

}

c->dg[i] = '';

c->length = a.length;

//printf("%d %sn", i, c->dg);

rm_lzeros(c);

//printf("%sn", c->dg);

}

void init(BN *a) {

a->sign = PLUS;

a->length = 1;

a->dg[0] = '0';

a->dg[1] = '';

}

int main(int argc, char** argv) {

BN m, n, rv;

if (argv[1][0] == '-') {

m.sign = MINUS;

sprintf(m.dg, "%s", &(argv[1][1]));

} else {

m.sign = PLUS;

sprintf(m.dg, "%s", argv[1]);

}

m.length = strlen(m.dg);

if (argv[2][0] == '-') {

n.sign = MINUS;

sprintf(n.dg, "%s", &(argv[2][1]));

} else {

n.sign = PLUS;

sprintf(n.dg, "%s", argv[2]);

}

n.length = strlen(n.dg);

printf("m:%c%sn", m.sign>0?' ':'-', m.dg);

printf("n:%c%sn", n.sign>0?' ':'-', n.dg);

add(m, n, &rv);

printf("m + n = %c%sn", rv.sign>0?' ':'-', rv.dg);

sub(m, n, &rv);

printf("m - n = %c%sn", rv.sign>0?' ':'-', rv.dg);

lshift(&rv, 1);

printf("m << 1 = %c%sn", rv.sign>0?' ':'-', rv.dg);

mul(m, n, &rv);

printf("m * n = %c%sn", rv.sign>0?' ':'-', rv.dg);

div(m, n, &rv);

printf("m / n = %c%sn", rv.sign>0?' ':'-', rv.dg);

}