2015/04/14

【C】大數 Big Numnbers





  • 何謂大數？

目前C只能存到最高64bit，大約是19位，超過即為大數。
在這邊先弄清楚各個type最多可存幾位
32bit- int：約9位
64bit - long long ：約19位


  • 如何評估運算之後會是幾位數？
2位數 + 3位數 <= 4位數
2位數 x 3位數 <= 5位數

  • 用陣列存大數，個位數靠前，後面要補0 (不補0也可，但要記長度)
e.g. 若我要存123456789

?
1
int num[MAX_LENGTH] = {9,8,7,6,5,4,3,2,1,0,0,0};

Code (十進位&百進位)
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define MAX_LENGTH 15
 
using namespace std;
 
void big_add(int *num1, int *num2, int *answer){
    int carry = 0;
    for (int i = 0; i < MAX_LENGTH; i++) {
        answer[i] = (num1[i]+num2[i]+carry)%10;
        carry = (num1[i]+num2[i]+carry)/10;
        /*answer[i] = (num1[i]+num2[i]+carry)%100;
        carry = (num1[i]+num2[i]+carry)/100;*/
    }
    if (carry != 0) printf("Overflow!\n");
}
 
void big_mul(int *num1, int *num2, int *answer){
    for(int i=0; i< MAX_LENGTH; i++) answer[i] = 0;
    int carry;
    for (int i=0; i< MAX_LENGTH; i++) {
        carry = 0;
        for (int j=0; j< MAX_LENGTH; j++) {
            if ((i+j) < MAX_LENGTH){ /*not overflow*/
                int tmp = answer[i+j]+num2[i]*num1[j]+carry;
                answer[i+j] = tmp%10;
                carry = tmp/10;
                /*answer[i+j] = tmp%10;
                carry = tmp/10;*/
            }
        }
    }
}
 
void big_sub(int *num1, int *num2, int *answer){
    /*num1>=num2且都為正*/
    int borrow = 0; //0或-1
    for (int i=0; i< MAX_LENGTH; i++) {
        answer[i] = num1[i]-num2[i]+borrow;
        if (answer[i] < 0){ //借位
            answer[i] += 10;
            //answer[i] += 100;
            borrow = -1;
        }
        else borrow = 0;
    }
    if (borrow != 0) printf("Underflow!\n");
}
 
void output(int *answer){
    int flag = 0;
    for (int i = MAX_LENGTH; i >= 0; i--) {
        if (answer[i]!=0 && flag==0) flag = 1;
        if (flag==1) printf("%d",answer[i]);
    }
    printf("\n");
}
 
int main(){
    int b[MAX_LENGTH] = {2,1,5,6,2,8,3,0,0,0,0,0,0,0,0};
    int a[MAX_LENGTH] = {3,7,8,9,3,2,5,0,0,0,0,0,0,0,0};
    /*int a[MAX_LENGTH] = {23,11,52,65,0,0,0,0,0,0,0,0,0,0,0};
    int b[MAX_LENGTH] = {37,72,86,91,0,0,0,0,0,0,0,0,0,0,0};*/
    int answer[MAX_LENGTH];
    big_add(a, b, answer);
    printf("ADD : "), output(answer);
    big_mul(a, b, answer);
    printf("MUL : "), output(answer);
    big_sub(a, b, answer);
    printf("SUB : "), output(answer);
    return 0;
}
於
標籤： ,