1
#include <stdio.h>
2
#include <stdlib.h>
3
#define MAX 200
4
5
typedef struct
6

{
7
int len;
8
int s[MAX+1];
9
} hp;
10
11
void 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
27
void 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
48
void 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
56
void 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
79
void 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
102
int 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
115
void 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
141
void 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
162
void 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
188
void 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
207
void 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
218
void 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) 编辑 收藏 引用