weitom1982

向各位技术前辈学习,学习再学习.
posts - 299, comments - 79, trackbacks - 0, articles - 0
  IT博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

大数运算全部源代码

Posted on 2006-03-20 23:26 高山流水 阅读(1443) 评论(7)  编辑 收藏 引用 所属分类: 计算机基础知识
这个程序应该是我在2004年写的
当时还只是一个读化工专业的大四学生
基本上对什么编程规范、什么算法,什么性能优化没什么了解
只是简单地用字符串模拟实现了任意大整数的四则运算
现在看来当然很幼稚了
不过为保持原来面目,一直没改,留做纪念。
供有需要的朋友参考
敬请指教




  1//long integer operation , inclue addition,substracttion,multiplicaton
  2//and division
  3#include <stdio.h>
  4#include <conio.h>
  5#include <ctype.h>
  6#include <string.h>
  7#define MAX 1000
  8#define MARK  ('0'-1)
  9
 10//The Prototypes of the functions
 11char* Initialiaze(char [],int);
 12int  Read(char [],char [],char * );
 13int  Print(char [],char [],char [],char []);
 14int  Calculate(char[],char[],char[],char []);
 15char* Addition(char[],char[]);
 16char* Substraction(char[],char[]);
 17char* Multiplication(char[],char[]);
 18char* Division(char[],char[]);
 19char Div_per_bit(char [],int , char []);
 20int Sub_per_bit(char [],char [],int *);
 21int Copy(char [],int ,char []);
 22int Compare(char [],char []);
 23int  Data_Process(char []);
 24int  Value(char);
 25int  Check(char []);
 26int  Compare(char [],char []);
 27int Judge(int);
 28int Convert(char [],char [],int);
 29
 30//The main function,calling  Read , Calculate  and Print function
 31int  main(void)
 32{    char a[MAX],b[MAX],c[2*MAX],action[MAX],ch='\t';
 33     while   (ch!=EOF)
 34     {
 35       clrscr();
 36       Read(a,b,action);
 37       if (Calculate(a,b,c,action))
 38         Print(a,b,c,action);
 39       ch=getchar();
 40     }

 41     return 0;
 42}

 43//The check function check if the input number is legal
 44int  Check(char s[])
 45{    int i;
 46     if (strlen(s)==0)
 47         return 0;
 48     if (strlen(s)>=MAX)
 49         return 0;
 50
 51     for (i=0; s[i]; i++)
 52       if (!isdigit(s[i]))
 53      return 0;
 54     return 1;
 55}

 56//The Iniatilize function ,initialize the result number before calculation
 57char* Initialize(char s[],int length)
 58{    int i;
 59     for (i=0; i<length; i++)
 60       s[i]=MARK;
 61     return s;
 62
 63}

 64//The Read function,Read the operands and the operation
 65int  Read(char a[],char b[],char action[])
 66{
 67     printf("************This Program calculats two long integer action!************\n");
 68     printf("Input long integer A,max length is %d:\n",MAX);
 69     gets(a);
 70     while (!Check(a))
 71     {   printf("Input error , Please input a correct value :\n");
 72     gets(a);
 73     }

 74     printf("Iuput the operation over a & b \n");
 75     printf("addition is '+' ,substraction is '-',multiplication is '*',division is '/'\n");
 76     printf("                            Warning:\n");
 77     printf("If you do the division,A must bigger than B ,and B must not equal to zero !\n");
 78     gets(action);
 79     while ((Compare(action,"+")!=0&& (Compare(action,"-")!=0&& (Compare(action,"*")!=0&& (Compare(action,"/")!=0))
 80     {   printf("Input error , Please input a correct action :\n");
 81         gets(action);
 82     }

 83     printf("Input long integer b,max length is %d:\n",MAX);
 84     gets(b);
 85     while (!Check(b))
 86     {   printf("Input error , Please input a correct value :\n");
 87     gets(b);
 88     }

 89     return 1;
 90}

 91//The Calculate function,calling Addition,Substraction,Multiplication or Division function  in accordance with the action
 92int  Calculate(char a[],char b[],char c[],char action[])
 93{
 94    if (Compare(action,"+")==0)
 95    {     strcpy(c,Addition(a,b));
 96         return 1;
 97    }

 98    if (Compare(action,"-")==0)
 99    {      if  ((Substraction(a,b))!=NULL)
100              strcpy(c,Substraction(a,b));
101          else
102          {      strcpy(c,"-");
103              strcat(c,Substraction(b,a));
104          }

105          return 1;
106    }

107    if (Compare(action,"*")==0)
108    {    strcpy(c,Multiplication(a,b));
109         return 1;
110    }

111
112    if (Compare(action,"/")==0)
113    {     if ((Division(a,b))!=NULL)
114            strcpy(c,Division(a,b));
115     else
116     {   printf("Press Ctrl-Z to end, Press Enter to recalculate!\n");
117         return 0;
118     }

119         return 1;
120     }

121
122}

123//The Print function , print the result
124int  Print(char a[],char b[],char c[],char action[])
125{    printf("The result of \n%s \n%s \n%s \nis :\n",a,action,b);
126     puts(c);
127     printf("Press Ctrl-Z to end , Press Enter  to recalculate..\n");
128     return 1;
129}

130//The Addition function , add two operands and return the result
131char* Addition(char a[],char b[])
132{    char c[2*MAX],d[2*MAX];
133     int i,j,k,a_length,b_length;
134     Initialize(c,2*MAX);
135     a_length=strlen(a);
136     b_length=strlen(b);
137     for (i=a_length-1,j=b_length-1,k=2*MAX-1; ( i>=0 || j>=0 ) ; i--,j--,k--)
138     {  if ( i>=0 && j>=0 )
139      c[k]=Value(a[i])+Value(b[j])+'0';
140    else
141      if (i>=0 && j<0 )
142         c[k]=Value(a[i])+'0';
143      else
144        if ( i<0 && j>=0 )
145           c[k]=Value(b[j])+'0';
146     }

147     Data_Process(c);
148     Convert(c,d,2*MAX);
149     return d;
150}

151//The Substraction function , substract one operand from another operand , and return the result
152char* Substraction(char a[],char b[])
153{    char c[2*MAX],d[2*MAX];
154     int i,j,k,a_length,b_length,sub_result,symbol,flag[2*MAX]={0};
155     Initialize(c,2*MAX);
156     a_length=strlen(a);
157     b_length=strlen(b);
158     if (strcmp(a,b)==0)
159    return ("0");
160     for (i=a_length-1,j=b_length-1,k=2*MAX-1; ( i>=0 || j>=0 ) ; i--,j--,k--)
161     {   sub_result=a[i]-b[j];
162     symbol=Judge(sub_result);
163     if (i>=1 && j>=0)
164     {      if (flag[k]==0)
165        {   if  (a[i]>=b[j])
166               c[k]=sub_result+'0';
167            else
168            {       c[k]=sub_result+10+'0';
169               flag[k-1]=1;
170            }

171        }

172        else
173        {   if (a[i]-b[j]>=1)
174              c[k]=sub_result-1+'0';
175            else
176            {     c[k]=sub_result+9+'0';
177              flag[k-1]=1;
178            }

179        }

180     }

181     else
182     if  (i==0 && j<0)
183        {
184             if (flag[k]==0)
185              c[k]=a[i];
186             else
187             {   if (a[i]==1)
188                ;
189             else
190                 c[k]=a[i]-1;
191             }

192        }

193     else
194     {  if ((i==0&& (j==0))
195           {   if (flag[k]==0)
196               {  switch (symbol)
197              {  case 0:   ;
198                       break;
199                 case 1:   c[k]=sub_result+'0';
200                       break;
201                 case -1:  return NULL;
202                       break;
203               }

204               }

205               else
206               {   switch (Judge(sub_result-1))
207               {  case 0:   ;
208                        break;
209                  case 1:   c[k]=sub_result-1+'0';
210                        break;
211                  case -1:  return NULL;
212                        break;
213               }

214               }

215           }

216         else
217         if ((i<0&& (j>=0))
218            return NULL;
219         else
220         if ((i>0&& (j<0))
221         {  if (flag[k]==0)
222              c[k]=a[i];
223            else
224            {   if (a[i]>'0')
225               c[k]=a[i]-1;
226            else
227            {  c[k]='9';
228               flag[k-1]=1;
229            }

230            }

231         }

232     }

233     }

234     Convert(c,d,2*MAX);
235     return d;
236}

237//The Multiplication function,multipy two operands and return the result
238char* Multiplication(char a[],char b[])
239{    char c[2*MAX],d[2*MAX];
240     int i,j,k,p,a_length,b_length;
241     Initialize(c,2*MAX);
242     a_length=strlen(a);
243     b_length=strlen(b);
244     for (j=b_length-1;  j>=0 ; j--)
245     {  k=2*MAX-(b_length-j);
246    for (i=a_length-1,p=k; i>=0; i--,p--)
247       if (c[p]==MARK)
248       {    c[p]=(Value(a[i]))*(Value(b[j]))%10+'0';
249            if (c[p-1]==MARK)
250                     c[p-1]=(Value(a[i]))*(Value(b[j]))/10+'0';
251                 else
252                     c[p-1]+=(Value(a[i]))*(Value(b[j]))/10;
253       }

254       else
255       {    c[p]+=(Value(a[i]))*(Value(b[j]))%10;
256            if (c[p-1]==MARK)
257                 c[p-1]=(Value(a[i]))*(Value(b[j]))/10+'0';
258            else
259                 c[p-1]+=(Value(a[i]))*(Value(b[j]))/10;
260       }

261    Data_Process(c);
262     }

263     Convert(c,d,2*MAX);
264     return d;
265
266}

267//The Division function,divise one operand from another operand, and return the result
268char* Division(char a[],char b[])
269{   char a1[MAX],c[MAX],d[MAX];
270    strcpy(a1,a);
271    int i,k,a_length=strlen(a1),b_length=strlen(b);
272    for (i=0; b[i]; i++)
273       if (b[i]!='0')
274      break;
275    if (i==strlen(b))
276
277    {    printf("Error!\nIf you do division,the dividend must not equal to zero!\n");
278        return 0;
279    }

280    if (Compare(a,b)==-1)
281    {    printf("Error!\nIf you do division, A must bigger than B!\n");
282    return 0;
283    }

284    for ( i=0,k=0; k<a_length-b_length+1; i++,k++)
285      c[k]=Div_per_bit(a1,b_length+i,b);
286    c[k]='\0';
287    Convert(c,d,MAX);
288    return d;
289
290}

291//The Div_per_bit function , calculate quotient per digit ,and return the result to Division function
292char Div_per_bit(char a[],int a_l,char b[])
293{   int i,j;
294    char c[MAX];
295    for (i=0,j=0; i<a_l; i++)
296      if ( a[i]!=MARK)
297      {   c[j]=a[i];
298      j++;
299      }

300    c[j]='\0';
301    for (i=0; c[i]; i++)
302       if (c[i]!='0')
303      break;
304    if (i==strlen(c))
305       return '0';
306    if (Compare(c,b)<0)
307       return '0';
308    if (Compare(c,b)==0)
309    {  for ( i=0; i<a_l; i++)
310      a[i]=MARK;
311       return '1';
312    }

313    i=0;
314    while (Compare(c,b)>=0)
315       Sub_per_bit(c,b,&i);
316    Copy(a,a_l,c);
317    return ('0'+i);
318
319}

320//The Sub_per_bit function, do the division by using substraction time after time
321int  Sub_per_bit(char a[],char b[],int *count)
322{    char c[MAX],d[MAX];
323     int i,j,k,a_length,b_length,sub_result,symbol,flag[MAX]={0};
324     Initialize(c,MAX);
325     a_length=strlen(a);
326     b_length=strlen(b);
327     if (strcmp(a,b)==0)
328    strcpy(c,"0");
329     for (i=a_length-1,j=b_length-1,k=MAX-1; ( i>=0 || j>=0 ) ; i--,j--,k--)
330     {   sub_result=a[i]-b[j];
331     symbol=Judge(sub_result);
332     if (i>=1 && j>=0)
333     {      if (flag[k]==0)
334        {   if  (a[i]>=b[j])
335               c[k]=sub_result+'0';
336            else
337            {       c[k]=sub_result+10+'0';
338               flag[k-1]=1;
339            }

340        }

341        else
342        {   if (a[i]-b[j]>=1)
343              c[k]=sub_result-1+'0';
344            else
345            {     c[k]=sub_result+9+'0';
346              flag[k-1]=1;
347            }

348        }

349     }

350     else
351     if  (i==0 && j<0)
352        {
353             if (flag[k]==0)
354              c[k]=a[i];
355             else
356             {   if (a[i]==1)
357                ;
358             else
359                 c[k]=a[i]-1;
360             }

361        }

362     else
363     {  if ((i==0&& (j==0))
364           {   if (flag[k]==0)
365               {  switch (symbol)
366              {  case 0:   ;
367                       break;
368                 case 1:   c[k]=sub_result+'0';
369                       break;
370                 case -1:  return 0;
371                       break;
372               }

373               }

374               else
375               {   switch (Judge(sub_result-1))
376               {  case 0:   ;
377                    break;
378                  case 1:   c[k]=sub_result-1+'0';
379                    break;
380                  case -1:  return 0;
381                    break;
382               }

383               }

384           }

385         else
386         if ((i<0&& (j>=0))
387         {  return 0;
388         }

389         else
390         if ((i>0&& (j<0))
391         {  if (flag[k]==0)
392              c[k]=a[i];
393            else
394            {   if (a[i]>'0')
395               c[k]=a[i]-1;
396            else
397            {  c[k]='9';
398               flag[k-1]=1;
399            }

400            }

401         }

402     }

403     }

404     Convert(c,d,MAX);
405     strcpy(a,d);
406     (*count)++;
407     return 1;
408}

409//The Copy function , copy  a number_string  to another , wipe off the inutility symbol
410int Copy(char a[],int a_l,char c[])
411{   int i,j,c_l=strlen(c);
412    for (i=0; i<a_l-c_l; i++)
413      a[i]=MARK;
414    for (i,j=0; j<c_l; i++,j++)
415      a[i]=c[j];
416    return 1;
417}

418//The Compare function ,compare two numbers and return the result
419int Compare(char a[],char b[])
420{   char c[MAX];
421    if ((strlen(a))>(strlen(b)))
422       return 1;
423    if ((strlen(a))==(strlen(b)))
424       return (strcmp(a,b));
425    if ((strlen(a))<(strlen(b)))
426       return -1;
427}

428
429//The Value function , receiver a digit_char, and return the number
430int Value(char c)
431{   if (isdigit(c))
432       return (c-'0');
433    else return 0;
434}

435//The Data_Process function,
436int Data_Process(char s[])
437{   int p,head,tail=2*MAX-1;
438    for (head=0; s[head]==MARK ; head++)
439      ;
440    for (p=tail; p>=head  ; p--)
441      if (!isdigit(s[p]))
442     if (s[p-1]!=MARK)
443     {  s[p-1]+=(s[p]-'0')/10;
444        s[p]=(s[p]-'0')%10+'0';
445     }

446     else
447     {  s[p-1]=(s[p]-'0')/10+'0';
448        s[p]=(s[p]-'0')%10+'0';
449     }

450     return 1;
451}

452//The Judeg function , judge the symbol of the number
453int Judge(int i)
454{   if (i==0)
455       return 0;
456    else
457       if (i>0)
458      return 1;
459       else
460      return  -1;
461}

462//The Convert function , convert the original result to the final result ,wipe off the inuility symbol and number
463int Convert(char c[],char d[],int length)
464{   int i,j;
465    for (i=0; i<length; i++)
466      if (c[i]==MARK || c[i]=='0')
467      ;
468      else
469     break;
470    for (i,j=0; i<length; i++,j++)
471      d[j]=c[i];
472    d[j]='\0';
473    return 1;
474}

475
posted on 2005-12-04 22:33 乖狗狗 阅读(422) 评论(8)  编辑 收藏收藏至365Key

FeedBack:
# re: 【原创】大数运算全部源代码
2005-12-07 01:29 | Lufer
值得学习,我到现在(大四)还没编写过这样的程序,准备先自己编出来再和您的比较下,有比较才有学习。

看了您在博客圆的blog,可以用QQ(5648806)和您交流一下吗?  回复
  
# re: 【原创】大数运算全部源代码
2005-12-08 21:32 | 乖狗狗
To Lufer
我现在上网的机会很少,因为工作很忙
有事情您可以在我的Blog上留言
我会尽快给您回复
相信这样会比用QQ交流更方便  回复
  
# re: 【原创】大数运算全部源代码
2005-12-09 22:00 | Lufer

乖狗狗,你好。

我现在签了慧通,大学毕业以后去成都的华为研究所工作,慧通的待遇对于一个没有经验的应届生而言算是可以了,但是最近我在网上(也包括您的另一个blog上)了解到一些慧通的信息,概括来说就是“工作时间长,劳动强度大”,甚至有人为工作而献出宝贵的生命。

我对我的这份工作有些担心,因为我的身体不算太好,最重要的是:我不知道慧通那“朝九晚九”的工作会给我留下多少自己的时间去看书,保持自己的竞争力。毕竟工作熟悉了以后,工作就差不多是体力劳动了(个人观点)……

您是一个过来人,能给我这个应届生说一下您认为工作之后怎么在那么少的个人时间里提升自己吗?刚进入工作之后最应该注意的又是什么呢?

感谢你工作之余给我的回复,您的回复将会是我不竭工作动力的一部分,谢谢!!!  回复
  
# re: 【原创】大数运算全部源代码
2005-12-10 22:55 | 乖狗狗
To Lufer
在华为或者慧通工作会很忙
所以你基本上没有自己的时间
不过,如果能够完成工作,你的核心竞争力已经很强了
慧通能学到的东西挺多
个人以为在这里是能够磨练一阵子的
在没毕业以前
建议你好好玩一玩,因为工作了以后,基本上都没有时间玩了

PS:我只是一个2005年毕业的“过来人”
  回复
  
# re: 【原创】大数运算全部源代码
2005-12-11 18:21 | Lufer
哦~原来你就是群里的南研啊,我的情况是不是跟你05年的情况差不多啊?

如果是的话,我想问一下技术方面的本科生在慧通里主要做什么具体工作,毕业前最好学点什么做为准备。面试的时候我应聘的软件研发工程师,但是面试官跟我说主要做测试工作(或许就是软件测试工程师吧),在这方面我很迷惑……

对于您的耐心回复非常感谢,谢谢!!!  回复
  
# re: 【原创】大数运算全部源代码
2005-12-12 22:29 | 乖狗狗
To Lufer
你现在学的东西和你以后做的东西可能会完全不一样
比如我之前学的C和C++
现在过来要用vxml和jsp,一切都要从头学起
至于岗位,我认为开发比测试要好
当然,这是我的个人之见
你在毕业之前。。。。。。。。有时间多玩玩吧


  回复
  
# re: 【原创】大数运算全部源代码
2006-02-10 14:24 | zdm
自己的特长和好的工作环境,哪个最重要呢?迷惑!  回复
  
# re: 【原创】大数运算全部源代码
2006-02-10 14:29 | fly
技术博客太单薄了,应该做的有点含金量才行啊。呵呵。。。建议。好的博客应该重点突出一个方面。如是齐头并进,看起来不太专业啊!  回复

Feedback

# 大数运算全部源代码   回复  更多评论   

2007-03-10 04:01 by 1986
中间有的代码丢失了,能补上完整的吗?

# 大数运算全部源代码   回复  更多评论   

2007-03-10 04:03 by 1986
我是一名即将毕业的大四学生,毕业设计方向就是大素数寻找,希望您给出中间遗漏掉的完整代码,3Q

# 大数运算全部源代码   回复  更多评论   

2007-03-10 04:36 by 1986
188行出现漏玛现象

# re: 大数运算全部源代码 [未登录]  回复  更多评论   

2007-03-12 17:44 by Tom
@1986
188:空着就可以,因为运算结束的值等于初始化的值.
这段代码我转载的,忘记出处了.本来想有时间调着玩来着,不知不觉过去这么久,什么都还没做.有时间我完整的调一下.

# re: 大数运算全部源代码   回复  更多评论   

2010-01-03 22:54 by 赤虎
非常感谢楼主的共享,此代码十分有用!

# re: 大数运算全部源代码   回复  更多评论   

2010-01-07 21:43 by 真實
請問能將它成讀檔input.txt裡的2個長數然後輸出到output.txt裡面嗎??

# re: 大数运算全部源代码   回复  更多评论   

2011-02-09 19:38 by lele-16
用上面的程序计算
3388495837466721394368393204672181522815830368604993048084925840555281177 ×1165882340667125990314837655838327081813101225814639260043952099413134433416292453

得不到正确结果:

395058745832651445264197678006144819960207764603049364541393760515793556265294

  50683609727842468219535093544305870490251995655335710209799226484977949442955603

  =
只有注册用户登录后才能发表评论。