1
#include <stdio.h>
2#include <stdlib.h>
3#define MAX 200
4
5typedef struct
6
{
7
int len;
8 int s[MAX+1];
9
} hp;
10
11void input(hp *a, int x) //读入数字
12{
13 int i;
14
15 a->len = 0;
16
17 while (x > 0)
18
{
19 a->s[1 + a->len++] = x % 10;
20 x /= 10;
21
}
22
23 for (i = a->len + 1; i <= MAX; i++)
24 a->s[i] = 0;
25}
26
27void input1(hp *a, char *str) //读入字符串
28{
29 int i, len;
30
31 a->len = 0;
32
33 if (str == NULL)
34 return;
35
36 len = strlen(str);
37
38 while (len > 0)
39 {
40 a->s[1 + a->len++] = *(str + len - 1) - '0';
41 len--;
42 }
43
44 for (i = a->len + 1; i <= MAX; i++)
45 a->s[i] = 0;
46}
47
48void print(hp *y) //打印数字
49{
50 int i;
51 for (i = y->len; i >= 1; i--)
52 printf("%d", y->s[i]);
53 printf("\n");
54}
55
56void add(hp *a, hp *b, hp *c) //高精度加法c = a + b
57{
58 int i, len;
59
60 for (i = 1; i <= MAX; i++) c->s[i] = 0;
61
62 if (a->len > b->len) len = a->len;
63 else len = b->len;
64
65 for (i = 1; i <= len; i++)
66 {
67 c->s[i] += a->s[i] + b->s[i];
68 if (c->s[i] >= 10)
69 {
70 c->s[i] -= 10;
71 c->s[i+1]++;
72 }
73 }
74
75 if (c->s[len+1] > 0) len++;
76 c->len = len;
77}
78
79void subtract(hp *a, hp *b, hp *c) //高精度减法c = a - b
80{
81 int i, len;
82
83 for (i = 1; i <= MAX; i++) c->s[i] = 0;
84
85 if (a->len > b->len) len = a->len;
86 else len = b->len;
87
88 for (i = 1; i <= len; i++)
89 {
90 c->s[i] += a->s[i] - b->s[i];
91 if (c->s[i] < 0)
92 {
93 c->s[i] += 10;
94 c->s[i+1]--;
95 }
96 }
97
98 while (len > 1 && c->s[len] == 0) len--;
99 c->len = len;
100}
101
102int compare(hp *a, hp *b) //高精度比较
103{
104 int len;
105
106 if (a->len > b->len) len = a->len;
107 else len = b->len;
108
109 while (len > 0 && a->s[len] == b->s[len]) len--;
110
111 if (len == 0) return 0;
112 else return a->s[len] - b->s[len];
113}
114
115void multiply(hp *a, int b, hp *c) //高精度 * 单精度
116{
117 int i, len;
118
119 for (i = 1; i <= MAX; i++) c->s[i] = 0;
120 len = a->len;
121
122 for (i = 1; i <= len; i++)
123 {
124 c->s[i] += a->s[i] * b;
125 c->s[i+1] += c->s[i] / 10;
126 c->s[i] %= 10;
127 }
128
129 len++;
130 while (c->s[len] >= 10)
131 {
132 c->s[len+1] += c->s[len] / 10;
133 c->s[len] %= 10;
134 len++;
135 }
136
137 while (len > 1 && c->s[len] == 0) len--;
138 c->len = len;
139}
140
141void multiplyh(hp *a, hp *b, hp *c) //高精度 * 高精度
142{
143 int i, j, len;
144
145 for (i = 1; i <= MAX; i++) c->s[i] = 0;
146
147 for (i = 1; i <= a->len; i++)
148 {
149 for (j = 1; j <= b->len; j++)
150 {
151 c->s[i+j-1] += a->s[i] * b->s[j];
152 c->s[i+j] += c->s[i+j-1] / 10;
153 c->s[i+j-1] %= 10;
154 }
155 }
156
157 len = a->len + b->len + 1;
158 while (len > 1 && c->s[len] == 0) len--;
159 c->len = len;
160}
161
162void power(hp *a, int b, hp *c) //高精度乘方c = a ^ b
163{
164 hp e;
165
166 if (b == 0)
167 {
168 c->len = 1;
169 c->s[1] = 1;
170 }
171 else if (b == 1)
172 {
173 memcpy(c, a, sizeof(hp));
174 }
175 else
176 {
177 power(a, b / 2, &e);
178 multiplyh(&e, &e, c);
179
180 if (b % 2 == 1)
181 {
182 memcpy(&e, c, sizeof(hp));
183 multiplyh(&e, a, c);
184 }
185 }
186}
187
188void divide(hp *a, int b, hp *c, int *d) //高精度 / 单精度 {d为余数}
189{
190 int i, len;
191
192 for (i = 1; i <= MAX; i++) c->s[i] = 0;
193 len = a->len;
194 *d = 0;
195
196 for (i = len; i >= 1; i--)
197 {
198 *d = *d * 10 + a->s[i];
199 c->s[i] = *d / b;
200 *d %= b;
201 }
202
203 while (len > 1 && c->s[len] == 0) len--;
204 c->len = len;
205}
206
207void multiply10(hp *a) //高精度 * 10
208{
209 int i;
210 for (i = a->len; i >= 1; i--)
211 a->s[i+1] = a->s[i];
212
213 a->s[1] = 0;
214 a->len++;
215 while (a->len > 1 && a->s[a->len] == 0) a->len--;
216}
217
218void divideh(hp *a, hp *b, hp *c, hp *d) //高精度 / 高精度{d为余数}
219{
220 hp e;
221 int i, len;
222
223 for (i = 1; i <= MAX; i++)
224 {
225 c->s[i] = 0;
226 d->s[i] = 0;
227 }
228
229 len = a->len;
230 d->len = 1;
231
232 for (i = len; i >= 1; i--)
233 {
234 multiply10(d);
235 d->s[1] = a->s[i];
236
237 while (compare(d, b) >= 0)
238 {
239 subtract(d, b, &e);
240 *d = e;
241 c->s[i]++;
242 }
243 }
244
245 while (len > 1 && c->s[len] == 0) len--;
246 c->len = len;
247}
posted on 2011-01-06 00:15
姚冰 阅读(3909)
评论(1) 编辑 收藏 引用