Zi 字媒體

[C/C++ 演算法]- 超長整數運算（大數運算） 剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。 拷貝來源：http://openhome.cc/Gossip/AlgorithmGossip/http://openhome.cc/Gossip/AlgorithmGossip/BigNumber.htm #include #include #define N 8 void add(int*, int*, int*); void subtract(int*, int*, int*); void multiply(int*, int, int*); void divide(int*, int, int*); void toComp(int*, int*); // 轉補數 void absv(int*, int*); // 轉絕對值 void print(int*); // 顯示大整數 int main(void) { int a[] = {0, 0, 0, 1234, 5678, 9910, 1923, 1124}; int b[] = {9999, 9999, 9999, 9999, 9999, 9999, 9999, 9901}; // -99 int c1[N], c2[N], c3[N], c4[N] = {0}; add(a, b, c1); print(c1); subtract(a, b, c2); print(c2); multiply(a, -3, c3); print(c3); divide(a, -3, c4); print(c4); return 0; } void add(int* a, int* b, int* c) { if(b[0] == 9999) { int comp[N] = {0}; toComp(b, comp); subtract(a, comp, c); } else { int i, carry = 0; for(i = N - 1; i >= 0; i--) { c[i] = a[i] + b[i] + carry; if(c[i] < 10000) { carry = 0; } else { // 進位 c[i] = c[i] - 10000; carry = 1; } } } } void subtract(int* a, int* b, int* c) { if(b[0] == 9999) { int comp[N] = {0}; toComp(b, comp); add(a, comp, c); } else { int i, borrow = 0; for(i = N - 1; i >= 0; i--) { c[i] = a[i] - b[i] - borrow; if(c[i] >= 0) { borrow = 0; } else { // 借位 c[i] = c[i] + 10000; borrow = 1; } } } } void multiply(int* a, int b, int* c) { // b 為乘數 int op1[N] = {0}; absv(a, op1); int op2 = abs(b); int i, tmp, carry = 0; for(i = N - 1; i >= 0; i--) { tmp = op1[i] * op2 + carry; c[i] = tmp % 10000; carry = tmp / 10000; } if((a[0] == 9999 && b > 0) || (a[0] == 0 && b < 0)) { toComp(c, c); } } void divide(int* a, int b, int *c) { // b 為除數 int op1[N] = {0}; absv(a, op1); int op2 = abs(b); int i, tmp, remain = 0; for(i = 1; i < N; i++) { tmp = op1[i] + remain; c[i] = tmp / op2; remain = (tmp % op2) * 10000; } if((a[0] == 9999 && b > 0) || (a[0] == 0 && b < 0)) { toComp(c, c); } } void toComp(int* src, int* comp) { int j; for(j = 0; j < N; j++) { comp[j] = 9999 - src[j]; } comp[N - 1] += 1; } void absv(int* src, int* op) { if(src[0] == 9999) { toComp(src, op); } else { int i; for(i = 0; i < N; i++) { op[i] = src[i]; } } } void print(int* c) { int v[N] = {0}; absv(c, v); if(c[0] == 9999) { printf("-"); } int isDropZero = 1; int i; for(i = 0; i < N; i++) { char s[5] = {'\0'}; sprintf(s, "d", v[i]); if(isDropZero) { int j; for(j = 0; s[j] == '0' && j < 4; j++); if(j < 4) { isDropZero = 0; for(; j < 4; j++) { printf("%c", s[j]); } } else if(i == N - 1) { printf("0"); } } else { printf(s); } } printf("\n"); }