转贴：大数的乘法

原贴地址：http://www.vchelp.net./cndevforum/subject_view.asp?subject_id=124450&forum_id=47

////////////////
3

#include <stdio.h>
4

#include <stdlib.h>
5

#include <string.h>
6

#include <ctype.h>
7

int cchkdig(char *r)
9

{
10

int i=0;
11

while(r[i]!='\0')
12

{
13

if(isdigit(r[i++])==0)
14

return (0);
15

}
16

return (1);
17

}
18

//去掉整数串表示前面多余的零，最后结果为空串时置为"0"
20

void cdel0(char *r)
21

{
22

unsigned int lr;
23

int i=0, j;
24

lr=strlen(r);
25

while(r[i]=='0')
26

++i;
27

if(i>0)
28

{
29

for(j=0; j<lr-i; ++j)
30

r[j]=r[j+i];
31

for(j=lr-i; j<lr; ++j)
32

{
33

r[j]='\0';
34

}
35

}
37

if(r[0]=='\0')
39

{
40

r[0]='0';
41

}
42

}
43

int scmp(char *r, char *u)
45

{
46

unsigned int lr, lu;
47

cdel0(r);
48

cdel0(u);
49

lr=strlen(r);
51

lu=strlen(u);
52

if(lr>lu)
54

{
55

return 1;
56

}
57

else if (lr<lu)
58

{
59

return -1;
60

}
61

return (strcmp(r, u));
62

}//end scmp()
64

//两个串表示数的减法
66

char *ssub(char *r, char *u)
67

{
68

unsigned int i,lr, lu, lp,c=0;
69

char h,hc;
70

char *p;
71

if(scmp(r, u)<0)
72

return NULL;
73

lr=strlen(r);
74

lu=strlen(u);
75

p=(char *)malloc((unsigned int)(lr+1)*sizeof(char));
76

for(i=0; i<lu; ++i)
77

{
78

h=r[lr-i-1]-u[lu-i-1]-c;
79

if(h<0)
80

{
81

c=1;
82

h=h+10;
83

}
84

else
85

c=0;
86

p[i]=h+'0';
87

hc=h+'0';
88

}
89

for (i=lu; i<lr; ++i)
90

{
91

h=r[lr-i-1]-'0'-c;
92

if(h<0)
93

{
94

c=1;
95

h=h+10;
96

}
97

else
98

c=0;
99

p[i]='0'+h;
100

hc='0'+h;
101

}
102

p[i]='\0';
103

lp=i-1;
104

105

while(p[lp]=='0'&&lp!=0)
106

{
107

p[lp]='\0';
108

lp--;
109

}
110

111

112

for(i=0; i<(lp+1)/2; ++i)
113

{
114

hc=p[i];
115

p[i]=p[lp-i];
116

p[lp-i]=hc;
117

}
118

return (p);
119

}//end ssub()
120

121

//两个串表示数的加法
122

char *sadd(char *r, char *u)
123

{
124

unsigned int lr, lu, lp;
125

int i, h, c=0;
126

char hc, *p;
127

lr=strlen(r);
128

lu=strlen(u);
129

if(lu>lr)
130

{
131

p=r;
132

r=u;
133

u=p;
134

h=lr;
135

lr=lu;
136

lu=h;
137

}
138

p=(char *)malloc((unsigned int)(lr+2)*sizeof(char));
139

for(i=0; i<lu; ++i)
140

{
141

h=r[lr-i-1]-'0'+u[lu-i-1]-'0'+c;
142

if(h>9)
143

{
144

c=1;
145

h=h-10;
146

}
147

else
148

c=0;
149

p[i]=h+'0';
150

}
151

for(i=lu; i<lr; ++i)
152

{
153

h=r[lr-i-1]-'0'+c;
154

if(h>9)
155

{
156

c=1;
157

h=h-10;
158

}
159

else
160

c=0;
161

p[i]='0'+h;
162

}
163

if(c>0)
164

{
165

p[i]=c+'0';
166

lp=i;
167

}
168

else
169

lp=i-1;
170

for(i=lp+1; i<lr+2; ++i)
171

p[i]='\0';
172

for(i=0; i<(lp+1)/2; ++i)
173

{
174

hc=p[i];
175

p[i]=p[lp-i];
176

p[lp-i]=hc;
177

}
178

return (p);
179

}//end sadd()
180

181

//两个串表示数的乘法
182

char *smut(char *r, char *u)
183

{
184

unsigned int lr, lu, lp;
185

int i, j, c, h;
186

char *p;
187

lr=strlen(r);
188

lu=strlen(u);
189

p=(char *)malloc((unsigned int)(lr+lu+1)*sizeof(char));
190

for(i=0; i<lr+lu; ++i)
191

p[i]='0';
192

p[lr+lu]='\0';
193

194

for(i=lr-1; i>=0; --i)
195

{
196

c=0;
197

for(j=lu-1; j>=0; --j)
198

{
199

lp=i+j+1;
200

h=(r[i]-'0')*(u[j]-'0')+p[lp]-'0'+c;
201

c=h/10;
202

h=h%10;
203

p[lp]=h+'0';
204

}
205

if(c>0)p[i+j+1]=c+'0';
206

}
207

208

cdel0(p);
209

return p;
210

}//end smut()
211

212

//两个串表示数的除法，结果精确到小数点后第n位
213

char *sdivf(char *u, char *v, int n)
214

{
215

char *p, *f, *r,*q;
216

unsigned int i, lu, lv, lr, iw, c, h;
217

int kh, j;
218

lu=strlen(u);
219

lv=strlen(v);
220

f=(char *)malloc((unsigned int)(lu+n+3)*sizeof(char));
221

q=(char *)malloc(sizeof(char));
222

for(i=0; i<lu+n+3; ++i)
223

f[i]='\0';
224

r=(char *)malloc((unsigned int)(lv+2)*sizeof(char));
225

for(i=0; i<lv+2; ++i)
226

r[i]='\0';
227

for(iw=0; iw<lu+n+2; ++iw)
228

{
229

if(iw<lu)
230

{
231

cdel0(r);
232

lr=strlen(r);
233

r[lr]=u[iw];
234

r[lr+1]='\0';
235

}
236

237

else if(iw>lu)
238

{
239

cdel0(r);
240

q[0]='0';
241

if(scmp(r, q)==0)
242

{
243

break;
244

}
245

lr=strlen(r);
246

r[lr]='0';
247

r[lr+1]='\0';
248

}
249

250

else
251

{
252

f[lu]='.';
253

continue;
254

}
255

256

kh=0;
257

while(scmp(r, v)>=0)
258

{
259

p=r;
260

r=ssub(p, v);
261

++kh;
262

}
263

f[iw]=kh+'0';
264

}
265

if(iw==lu+n+2)
266

{
267

if(f[lu+n+1]>='5')
268

{
269

f[lu+n+1]='\0';
270

c=1;
271

for(j=lu+n; j>=0; --j)
272

{
273

if(c==0)
274

{
275

break;
276

}
277

if(f[j]=='.')
278

{
279

continue;
280

}
281

h=f[j]-'0'+c;
282

if(h>9)
283

{
284

h=h-10;
285

c=1;
286

}
287

else
288

c='\0';
289

f[j]=h+'0';
290

}
291

}
292

else
293

f[lu+n+1]='\0';
294

295

}
296

free(r);
297

free(p);
298

q=NULL;
299

free(q);
300

cdel0(f);
301

return(f);
302

}//end sdivf()
303

304

//两个串表示数的除法，结果分别用整商与余数表示
305

char *sdivkr(char *u, char *v, char **rout)
306

{
307

char *f, *r;
308

unsigned int i, lu, lv, lr, iw;
309

int kh;
310

lu=strlen(u);
311

lv=strlen(v);
312

313

f=(char *)malloc((unsigned int)(lu+1)*sizeof(char));
314

for(i=0; i<lu+1; ++i) f[i]='\0';
315

r=(char *)malloc((unsigned int)(lv+2)*sizeof(char));
316

for(i=0; i<lv+2; ++i) r[i]='\0';
317

318

for(iw=0; iw<lu; ++iw)
319

{
320

cdel0(r);
321

lr=strlen(r);
322

r[lr]=u[iw];
323

r[lr+1]='\0';
324

kh=0;
325

while(scmp(r, v)>=0)
326

{
327

r=ssub(r, v);
328

++kh;
329

}
330

f[iw]=kh+'0';
331

}
332

cdel0(r);
333

*rout=r;
334

cdel0(f);
335

return(f);
336

337

}//end *sdivkr()
338

339

//调用上述函数实现两任意长正整数任意指定精度的算术计算器程序
340

void main(int argc, char *argv[])
341

{
342

char *p, *r;
343

int n;
344

if(argc!=4)
345

{
346

if(argc!=3)
347

printf("\n>>\"order n1 op n2\" or n ! ");
348

exit(0);
349

}
350

cdel0(argv[1]);
351

if(cchkdig(argv[1])==0)
352

{
353

printf("Input data error, Input again!");
354

exit(0);
355

}
356

cdel0(argv[3]);
357

if(cchkdig(argv[3])==0)
358

{
359

printf("Input data error, Input again!");
360

exit(0);
361

}
362

363

if(strcmp(argv[2], "+")==0)
364

{
365

printf("%s", p=sadd(argv[1], argv[3]));
366

free(p);
367

}
368

369

else if(strcmp(argv[2], "-")==0)
370

{
371

printf("%s", p=ssub(argv[1], argv[3]));
372

free(p);
373

}
374

375

else if(strcmp(argv[2], "*")==0)
376

{
377

printf("%s", p=smut(argv[1], argv[3]));
378

free(p);
379

}
380

381

else if(argv[2][0]=='/' && strlen(argv[2])==1)
382

{
383

if(argv[3][0]=='0')
384

{
385

printf("error!devided by zero!!\n");
386

exit(0);
387

}
388

p=sdivkr(argv[1], argv[3], &r);
389

printf("k=%s r=%s", p, r);
390

free(p);
391

free(r);
392

}
393

394

else if(argv[2][0]=='/'&&strlen(argv[2])>1)
395

{
396

if(argv[3][0]=='0')
397

{
398

printf("error!devided by zero!!\n");
399

exit(0);
400

}
401

402

argv[2][0]='\0';
403

cdel0(argv[2]);
404

if(cchkdig(argv[2])==0)
405

{
406

printf("Input data error, Input again!");
407

exit (0);
408

}
409

n=atoi(argv[2]);
410

printf("%s", p=sdivf(argv[1], argv[3], n));
411

free(p);
412

}
413

414

415

}