大数加法、乘法

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 
  5 // x1 + x2 = yy
  6 int add_1(char *x1, char *x2, char *yy)
  7 {
  8     int x1_len, x2_len, x_max, yy_len;
  9     int i, j, carry, tt;
 10     char *y1;
 11     
 12     x1_len = strlen(x1);
 13     x2_len = strlen(x2);
 14     
 15     //printf("x1_len:%d, x2_len:%d\r\n", x1_len, x2_len);
 16     
 17     x_max = x1_len > x2_len ? x1_len : x2_len;
 18     // yy_len的最大长度为: x_max+1
 19     // yy_len的最小长度为: x_max
 20     if((y1 = malloc(sizeof(char) * (x_max + 2))) == NULL)
 21     {
 22         return 0;    
 23     }
 24     memset(y1, 0x00, x_max + 2);
 25     
 26     carry  = 0;
 27     yy_len = 0;
 28     for(i=x1_len, j=x2_len; i > 0 && j > 0; i--, j--, yy_len++)
 29     {
 30         tt = (x1[i-1]-‘0‘) + (x2[j-1]-‘0‘) + carry;
 31         y1[yy_len] = (tt % 10) + ‘0‘;
 32         carry = tt / 10;
 33     }
 34     for(; i > 0; i--, yy_len++)
 35     {
 36         tt = (x1[i-1]-‘0‘) + carry;
 37         y1[yy_len] = (tt % 10) + ‘0‘;
 38         carry = tt / 10;            
 39     }
 40     for(; j > 0; j--, yy_len++)
 41     {
 42         tt = (x2[j-1]-‘0‘) + carry;
 43         y1[yy_len] = (tt % 10) + ‘0‘;
 44         carry = tt / 10;            
 45     }
 46     if(carry != 0)
 47     {
 48         y1[yy_len++] = carry + ‘0‘;
 49     }
 50     
 51     //printf("yy_len: %d\r\n", yy_len);
 52     
 53     for(i = 0; i < yy_len; i++)
 54     {
 55         yy[i] = y1[yy_len-i-1];
 56     }
 57     yy[yy_len] = ‘\0‘;
 58     
 59     free(y1);
 60 
 61     return yy_len;
 62 }
 63 
 64 // x1 + x2 = yy 
 65 int add_2(char *x1, char *x2, char *yy)
 66 {
 67     int x1_len, x2_len, x_max, yy_len;
 68     int i, tmp, carry;
 69     char *y1;
 70     
 71     x1_len = strlen(x1);
 72     x2_len = strlen(x2);
 73     //printf("x1_len:%d, x2_len:%d\r\n", x1_len, x2_len);
 74 
 75     x_max = x1_len > x2_len ? x1_len : x2_len;
 76 
 77     if((y1 = malloc(sizeof(char) * (x_max + 2))) == NULL)
 78     {
 79         return 0;    
 80     } 
 81 
 82     carry = 0;
 83     yy_len = 0;
 84     
 85     while(x1_len > 0 && x2_len > 0)
 86     {
 87         tmp = x1[--x1_len] + x2[--x2_len] - 2 * ‘0‘ + carry;
 88         y1[yy_len++] = tmp % 10 + ‘0‘;
 89         carry  = tmp / 10;
 90     }
 91     while(x1_len > 0)
 92     {
 93         tmp = x1[--x1_len] - ‘0‘ + carry;
 94         y1[yy_len++] = tmp % 10 + ‘0‘;
 95         carry  = tmp / 10;
 96     }
 97     while(x2_len > 0)
 98     {
 99         tmp = x2[--x2_len] - ‘0‘ + carry;
100         y1[yy_len++] = tmp % 10 + ‘0‘;
101         carry  = tmp / 10;     
102     }
103     if(carry != 0)
104     {
105         y1[yy_len++] = carry + ‘0‘;
106     }
107 
108     //printf("yy_len: %d\r\n", yy_len);
109     
110     for(i = 0; i < yy_len; i++)
111     {
112         yy[yy_len-i-1] = y1[i];
113     }
114     yy[yy_len] = ‘\0‘;
115 
116     free(y1);
117 
118     return yy_len;
119 }
120 
121 // x1 * x2 = yy
122 int mult(char *x1, char *x2, char *yy)
123 {
124     int x1_len, x2_len, yy_len;
125     int i, carry, pos, tt;
126     char *pp;
127     char *y1;
128 
129     x1_len = strlen(x1);
130     x2_len = strlen(x2);
131     
132     //printf("x1_len: %d, x2_len:%d\r\n", x1_len, x2_len);
133     
134     // yy_len的最大长度为: x1_len+x2_len;
135     // yy_len的最小长度为: x1_len+x2_len-1;
136     if((y1 = malloc(sizeof(char) * (x1_len+x2_len+1))) == NULL)
137     {
138         return 0;    
139     }
140     memset(y1, 0x00, x1_len+x2_len+1);
141         
142     for(pos = 0; x2_len > 0; x2_len--, pos++)
143     {
144         carry = 0;
145         pp = &y1[pos];
146         
147         for(i = x1_len; i > 0; i--)
148         {
149             // 当前位的乘积+进位位+原有位
150             tt    = (x2[x2_len-1]-‘0‘) * (x1[i-1]-‘0‘) + carry + (*pp);
151             *pp++ = tt % 10;
152             carry = tt / 10;
153         }
154         
155         if(carry != 0)
156         {
157             *pp++ = carry;
158         }
159     }
160     
161     yy_len = pp - y1;
162     //printf("yy_len: %d\r\n", yy_len);
163 
164     while(y1[yy_len-1] == 0 && yy_len > 0)
165     {
166         yy_len--;
167     }
168     if(yy_len == 0)
169     {
170         yy_len = 1;
171     }
172 
173     for(i = 0; i < yy_len; i++)
174     {
175         yy[yy_len-i-1] = y1[i] + ‘0‘;
176     }
177     yy[yy_len] = ‘\0‘;
178 
179     free(y1);
180 
181     return yy_len;
182 }
183 
184 int main(void)
185 {
186 #define MAX_LEN     (100)
187     char *x1 = "999";
188     char *x2 = "999";
189     char *yy;
190 
191     yy = malloc(sizeof(char) * MAX_LEN);
192 
193     memset(yy, 0x00, sizeof(char)*MAX_LEN); 
194     add_1(x1, x2, yy);
195     printf("%s + %s = %s\r\n", x1, x2, yy);
196 
197     memset(yy, 0x00, sizeof(char)*MAX_LEN); 
198     add_2(x1, x2, yy);
199     printf("%s + %s = %s\r\n", x1, x2, yy);
200 
201     memset(yy, 0x00, sizeof(char)*MAX_LEN); 
202     mult(x1, x2, yy);
203     printf("%s * %s = %s\r\n", x1, x2, yy);
204 
205     return 0;
206 }