找回密码
 欢迎注册
查看: 17635|回复: 14

[原创] 笔算除法的代码

[复制链接]
发表于 2015-1-29 13:21:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
包括本人在内的大数运算爱好者,都喜欢自己写出大整数的加、减、乘、除的程序。很多的爱好者都对笔算除法望而却步,主要原因是程序实现过程中对笔算除法的对位不准。
本人通过自己揣摩,找到了一种高效的笔算除法方法,并给出源码。
说明:1) 通过数学原理,对笔算除法找到了一种最优实现途径。
           2) 程序实现过程中对源码未进行任何优化。
          3) 程序以函数的方式说明实现过程。
        
编译环境:vc++6.0
操作系统:windows xp 3
机器性能:AMD Athlon(tm) II X2  250
                  Processor
                  3.0GHz     2.00G的内存

测试条件:8000位十进制数除以4001位十进制数,给出商和余数,被除数、除数、商和余数都输出到文件,方便第三方软件检验。debug模式。
测试结果:47ms.(不计输出时间。)

附程序代码;(如果使用其它编译器,请确保每个存贮单元为32bite的容量)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <time.h>
  5. #include <windows.h>

  6. int main()
  7. {
  8.         
  9.     int   dividend[2000]={0};     // 被除数      dividend
  10.     int         Cdiv[2000]={0};   // 被除数镜像  copy_dividend
  11.     int         divR[1000]={0};   // 除数        divisor
  12.     int        result[1002]={0};  // 乘积的结果  result
  13.     int             qut[999]={0}; // 商          quotient     
  14.     int           CTRL[12]={0};   // 控制        control

  15.     int  t1,t2;                   // 时间        time
  16.    unsigned int seed;             // 初始化随机函数的发生器
  17.     int temp,f0,i;  

  18. void control_neno(int *Cdiv,int *qut,int *CTRL);
  19. void quotient_MUL_divisor(int *result,int *divR,int *CTRL);
  20. void dividend_SUB_result(int *Cdiv,int *result,int *divR,int *CTRL);
  21. void OUT_text(int *dividend,int *divR,int *qut,int *Cdiv,int *CTRL);
  22. void ArraysFormat();


  23.         seed=time(0);//=======以下部分用来随机产生两个大数。代替  ArraysFormat();
  24.     srand(seed);

  25.         Cdiv[0]=3141;  //------------共产生8000位十进制数,作为被除数。存入数组Cdiv[]中。
  26.         dividend[0]=3141;
  27.         for(i = 1; i<2000; i++)
  28.         {
  29.                 Cdiv[i]=(rand())%10000;
  30.                 dividend[i]=Cdiv[i];
  31.         }

  32.         divR[0]=27182;  //------------共产生4001位十进制数。作为除数。存入数组divR[]中。
  33.         for(i = 1; i<1000; i++)
  34.                 divR[i]=(rand())%10000;
  35. t1=GetTickCount();//时间计时开始;

  36.           CTRL[0]=0;           //试商由1变为0时的判断依据。CTRL[0]=1时表示试商由1变为0
  37.           CTRL[1]=1000;        //除数的个数。
  38.           CTRL[2]=CTRL[1]-1;   //除数数组的最大下标。
  39.         //CTRL[3]                未定义。
  40.         //CTRL[4]                总的循环控制变量。
  41.         //CTRL[5]                余数的符号
  42.         //CTRL[6]                每次循环参与计算的被除数起始位下标。
  43.         //CTRL[7]                试商的值。
  44.         //CTRL[8]                余数从左端起非零第一项的位置。
  45.         //CTRL[9]                每次循环参与计算的被除数个数。
  46.           CTRL[10]=1001;       //余数剩下的位数。

  47.           ArraysFormat();
  48.    
  49. while(CTRL[4]<=999)        //-----(CTRL[4]<=len(Cdiv[])-len(divR[])-1)
  50. {
  51.         f0=CTRL[6];
  52.         CTRL[9]=1001;

  53.         temp=(Cdiv[f0]*10000+Cdiv[f0+1])/divR[0];  // 求试商
  54.         if((temp==0)||((temp==1)&&(CTRL[0]==1)))
  55.                 {
  56.                         if(CTRL[10]<CTRL[1]+1)
  57.                         {
  58.                                 qut[CTRL[4]]=0;
  59.                                 CTRL[4]++;
  60.                         }
  61.                
  62.                         CTRL[9]++;
  63.                         temp=(Cdiv[f0]*100000000+Cdiv[f0+1]*10000+Cdiv[f0+2])/divR[0]; //试商等于零,增加一项再求商。
  64.                 }
  65.                 CTRL[7]=temp;

  66.                  quotient_MUL_divisor(result,divR,CTRL);////乘法函数

  67.                  dividend_SUB_result(Cdiv,result,divR,CTRL);////减法函数

  68.                 if(CTRL[5]>=0)
  69.                 {
  70.                         qut[CTRL[4]]=temp;
  71.                         CTRL[0]=0;
  72.                 }
  73.                 else
  74.                 {
  75.                         qut[CTRL[4]]=temp-1;
  76.                         if(temp==1)
  77.                         {
  78.                                 CTRL[0]=1;
  79.                         }
  80.                         else
  81.                         {
  82.                                 CTRL[0]=0;
  83.                         }
  84.                         
  85.                 }

  86.         CTRL[4]++;
  87.     control_neno(Cdiv,qut,CTRL);//商0的函数
  88.         
  89. }

  90. t2=GetTickCount();//时间计时结束。
  91.       
  92.         OUT_text(dividend,divR,qut,Cdiv,CTRL);//输出函数

  93.         printf("被除数已输出到e盘的dividend.txt 文件中。\n");
  94.         printf("除数已输出到e盘的divisor.txt 文件中。\n");
  95.         printf("商已输出到e盘的quotient.txt 文件中。\n");
  96.         printf("余数已输出到e盘的remainder.txt 文件中。\n");

  97.                 printf("时间%d ms\n",t2-t1);

  98.   return 0;
  99. }

  100. void quotient_MUL_divisor(int *result,int *divR,int *CTRL)
  101. {
  102.         int i,temp=0,n;

  103.         n=CTRL[9]-CTRL[1];
  104.         result[0]=0;
  105.         result[1]=0;

  106.         for(i=CTRL[2];i>=0;i--)
  107.                 result[i+n]=divR[i]*CTRL[7];

  108.         for(i=CTRL[2]+n;i>=1;i--)
  109.         {
  110.                 temp=result[i]/10000;
  111.                 result[i-1]=result[i-1]+temp;
  112.                 result[i]=result[i]-temp*10000;
  113.         }
  114.         return ;
  115. }

  116. void dividend_SUB_result(int *Cdiv,int *result,int *divR,int *CTRL)
  117. {
  118.         int i,temp=0,n,j;
  119.         int carry[1002]={0};

  120.         n=CTRL[9]-CTRL[1];

  121.         for(i=CTRL[2]+n;i>=0;i--)
  122.         {
  123.                 carry[i]=Cdiv[i+CTRL[6]]-result[i]-temp;
  124.                 temp=0;
  125.                 if(carry[i]<0)
  126.                 {
  127.                         carry[i]=carry[i]+10000;
  128.                         temp=1;
  129.                 }
  130.         }
  131.         CTRL[5]=1;

  132.         if(temp==1)
  133.         {
  134.                         for(i=CTRL[2];i>=0;i--)
  135.                                 carry[i+n]=divR[i]+carry[i+n];

  136.                                 for(i=CTRL[2]+n;i>=1;i--)
  137.                                 {
  138.                                         temp=carry[i]/10000;
  139.                                         carry[i-1]=carry[i-1]+temp;
  140.                                         carry[i]=carry[i]-temp*10000;
  141.                                 }
  142.                         carry[0]=carry[0]-10000;        
  143.                
  144.                 CTRL[5]=-1;
  145.         }


  146.         for(i=0;i<=CTRL[2]+n;i++)
  147.                         Cdiv[i+CTRL[6]]=carry[i];

  148.                 j=0;  //计算余数从左端起非零第一项的位置。
  149.                 while((carry[j]==0) && (j<=CTRL[2]+n))
  150.                         j++;

  151.                 CTRL[6]=CTRL[6]+j;
  152.                 CTRL[8]=j;         
  153.                 CTRL[10]=CTRL[1]+n-j;
  154.                
  155.                 return ;
  156. }

  157. void control_neno(int *Cdiv,int *qut,int *CTRL)
  158. {
  159.         int i,j,m,s;

  160.         if(CTRL[10]>0)
  161.         {
  162.                 m=CTRL[1]-CTRL[10];
  163.                 for(i=m;i>=1;i--)
  164.                 {
  165.                         qut[CTRL[4]]=0;
  166.                         CTRL[4]++;
  167.                 }
  168.         }
  169.     if(CTRL[10]==0)
  170.         {
  171.         
  172.                 s=0;//计算j 的个数。
  173.                 j=CTRL[6]-CTRL[8]+CTRL[9];
  174.                 while(Cdiv[j]==0)
  175.                 {
  176.                         j++;
  177.                         s++;
  178.                 }

  179.                 CTRL[6]=j;
  180.                 m=s+CTRL[1];
  181.         
  182.                 for(i=1;i<=m;i++)
  183.                 {
  184.                         qut[CTRL[4]]=0;
  185.                         CTRL[4]++;
  186.                 }

  187.         }
  188.         return ;
  189. }

  190. void OUT_text(int *dividend,int *divR,int *qut,int *Cdiv,int *CTRL)
  191. {
  192.         int i;
  193.         FILE  *fp;                   // 输出数据到文件

  194.         if((fp=fopen("e:\\dividend.txt","w"))==NULL)
  195.         {
  196.                 printf("not open dividend.txt");
  197.                 exit(0);
  198.         }
  199.         for(i=0;i<2000;i++)
  200.                 fprintf(fp,"%04d",dividend[i]);//输出被除数。

  201.         if((fp=fopen("e:\\divisor.txt","w"))==NULL)
  202.         {
  203.                 printf("not open divisor.txt");
  204.                 exit(0);
  205.         }
  206.         for(i=0;i<1000;i++)
  207.                 fprintf(fp,"%04d",divR[i]);//输出除数。

  208.         if((fp=fopen("e:\\quotient.txt","w"))==NULL)
  209.         {
  210.                 printf("not open quotient.txt");
  211.                 exit(0);
  212.         }
  213.         for(i=0;i<1000;i++)
  214.                 fprintf(fp,"%04d",qut[i]);//输出商。


  215.         if((fp=fopen("e:\\remainder.txt","w"))==NULL)
  216.         {
  217.                 printf("not open remainder.txt");
  218.                 exit(0);
  219.         }
  220.         for(i=CTRL[6];i<2000;i++)
  221.                 fprintf(fp,"%04d",Cdiv[i]);//输出余数。

  222.         fclose(fp);
  223.         return ;
  224. }

  225. void ArraysFormat()
  226. {
  227.                   //这个函数将键盘、文件输入的数字字符串转化为数字,存入数组中,
  228.                   //每个存贮单元中存入四位十进制数。
  229.                   //除数的第一位(最高位)需确保五位十进制数。
  230. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-1-30 08:00:15 | 显示全部楼层
Line73: Cdiv[f0]*100000000
在int下,有整数溢出风险,你可注意到?或者,楼主可对输出结果验证过?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-1-30 11:02:04 | 显示全部楼层
Line73: Cdiv[f0]*100000000
在int下,有整数溢出风险,你可注意到?或者,楼主可对输出结果验证过?

谢谢郭先生关注。
说明:1)不会溢出,因为试商是取被除数的前两项来做除法,即Cdiv[0]和Cdiv[1],单看这两项的数学表达式是Cdiv[0]x10000+Cdiv[1]。而除数是divR[0],它是确保的五位十进制数,所以相除的结果要么大于零,这时程序绕开line73行。相除的结果如果等于零,说明Cdiv[0]x10000+Cdiv[1]这两项最多只有五位十进制数。Cdiv[1]占了四位十进制数,那么Cdiv[0]只有一位十进制数。这时程序才能进入line73行。这时Cdiv[f0]*100000000就是成立的。
         2)测试过,用的是笨办法,先运行这个程序一次,再用vb写的除法----------方法是“循环相减”求商,这样很慢,但能保证结果是正确的----------求出商来对照。用眼睛一行一行的扫,还未发现错误。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-1-30 15:39:07 | 显示全部楼层
我的几点建议:

在实际应用中,除法函数的接口的定义应该有2种,第1种是只求商,第2种是求商和余数。

1. 接口,在第一种情况下,传入参数有3个
1). 被除数(只读)
2). 除数(只读)
3). 商(可写)

2. 关于工作空间:
  工作空间只需要一个比被除数长度稍大一点的数组,即楼上提到的“被除数的镜像”。可使用栈(当被除数长度较小时)或者动态分配(当被除数长度很大时)。被除数 减去 部分商(每次试出得到的商)乘以除数的积的差可直接完成,不需要中间结果数组result。

3. 代码优化。程序逻辑仍可优化,你的代码稍显复杂。  
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-1-30 16:30:38 | 显示全部楼层
我的几点建议:

谢谢liangbch的关注:
    1)首先接受先生的建议。我会慢慢的优化一下,我只是爱好,实际上没有编程的功力。能不能优化得好,还是未知。
    2)我写程序慢,这个程序更是伤脑筋,这个程序基本上是靠调试调出来的。原因是除法的各种可能都要考虑到,脑袋一片模糊,就像先生所说的,程序的逻辑没有理清。
    3)因为我写得慢,所以过一段时间,我把这个程序改一改,让它能处理数据。
   

发现这个程序的一个错误,就是当整除时,不能输出余数“0”,要把输出余数的语句改一改才行。

  1. if(CTRL[6]<2000)
  2.          {
  3.                 for(i=CTRL[6];i<2000;i++)
  4.                         fprintf(fp,"%04d",Cdiv[i]);//输出余数。
  5.          }
  6.          else
  7.          {
  8.                 fprintf(fp,"%d",0);//输出余数。
  9.          }
复制代码

把输出余数的语句改成这样就可以了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-2-16 23:11:40 | 显示全部楼层
本帖最后由 只是呼吸 于 2015-2-17 00:11 编辑

根据liangbch的建议,我把程序作了修改。修改后的程序能处理任意两个不超过8000位数(十进制数)的整数除法。由于增加了从屏幕输入的语句,所以程序太长,不清晰,只好分成两部分:前一部分把屏幕输入的字符转化为数组,后一部分把数组相除得到结果。程序中给出全部注释。给出笔算除法的实现步骤。
    笔算除法的实现步骤:
       1) 输入字符串a
       2)输入字符串b
       3)转化字符串a为被除数数组A,每4个数字为一组,(万进制)
       4)转化字符串b为除数数组B,每4个数字为一组,但第一个元素B[0]必须是5位十进制数。
       5)除法开始:
       6)求试商:n=(A[0]*10000+A[1])/B[0]
       7)做乘法:C=B*n
       8)做减法:D=A-C
       9)判断:if(D>=0)
                     则n就是准确商。
       10)把余数D和未参与计算的A组成新的A
       11)if(D<0)
                则n-1就是准确商。
       12)做加法,D=D+B  (把负的余数转变为正的)
       13)把余数D和未参与计算的A组成新的A
       14)返回5
       15)程序结束,输出商和余数。

我用的是vc++6.0,采用分别编译的方式,给出商和余数。

  1. #include <stdio.h>
  2. #include <string.h>

  3. int main()
  4. {
  5. extern void BigDigit_DIV(int *dividend,int LENdividend, int *divR,int LENdivR,int AddZero);         //外部函数,函数功能:将两个数相除得到结果

  6. void string_digitArray(char *a,char *b,int *ArrayA,int *ArrayB,int *LEN_A,int *LEN_B,int *Add_Zero);//内部函数,函数功能:将两个字符串转化为数组
  7. int digit_control(char a[]);                                                                        //内部函数,函数功能:控制数字规模  
  8. int count_zero(char b[]);                                                                           //内部函数,函数功能:统计0的个数                                                                       
  9. void Vary(char a[],int pr[],int AddZero);                                                           //内部函数,函数功能:转化字符串为数组

  10.         int ArrayA[2010]={0};    //被除数
  11.         int ArrayB[2010]={0};    //除数
  12.         int quotient[2010]={0};  //商
  13.         //int rm[2010]={0};        //余数

  14.         int LEN_ArrayA,LEN_ArrayB,AddZero;
  15.         int *LEN_A,*LEN_B,*Add_Zero;
  16.         char a[10010];
  17.         char b[10010];

  18.         LEN_A=&LEN_ArrayA;
  19.         LEN_B=&LEN_ArrayB;
  20.         Add_Zero=&AddZero;

  21.         string_digitArray(a,b,ArrayA,ArrayB,LEN_A,LEN_B,Add_Zero);//把字符串a,b,转化为数字数组ArrayA,ArrayB,并返回数组的最大下标,每个元素中存4个十进制数字。
  22.         BigDigit_DIV(ArrayA,LEN_ArrayA,ArrayB,LEN_ArrayB,AddZero);

  23. return 0;
  24. }


  25. void Vary(char dm[],int kk[],int ss,int yy)   //转化字符串A为数组存入kk[]中
  26. {
  27.         int r,s,kd;
  28.         r=0;                          
  29.         if (yy==0)
  30.         {
  31.                 for(s=0;s<=ss;s++,r+=4)
  32.                         kk[s]=dm[r]*1000+dm[r+1]*100+dm[r+2]*10+dm[r+3]-53328;
  33.         }
  34.         else
  35.         {
  36.                 for (kd=0;kd<=yy-2;kd++)
  37.                 {
  38.                         kk[0]+=dm[kd]-48;
  39.                         kk[0]*=10;
  40.                 }
  41.                 kk[0]+=dm[yy-1]-48;

  42.                 for(s=1;s<=ss;s++,yy+=4)
  43.                         kk[s]=dm[yy]*1000+dm[yy+1]*100+dm[yy+2]*10+dm[yy+3]-53328;
  44.         }
  45. }

  46. int count_zero(char b[])
  47. {
  48.         int j,s;
  49.         j=strlen(b);
  50.         s=0;
  51.         while(b[s]=='0')//找出除数中第一个非零的数的位置
  52.                 s++;
  53.         j=j-s;//求出非零的实际长度。
  54.         return j;
  55. }

  56. int digit_control(char a[])
  57. {
  58.         int t,i,s,lenA;
  59.         i=strlen(a);//计算输入数组中的数字位数。
  60.         for(s=0;s<i;s++)
  61.         {
  62.                 if(isdigit(a[s])==0)
  63.                 {
  64.                         printf("输入的符号中有数字以外的其它字符,请重新输入\n");
  65.                         t=1;
  66.                         break;
  67.                 }
  68.         }

  69.         if(t!=1)
  70.         {
  71.                 lenA=count_zero(a);//求出非零位数
  72.                 if(lenA>8000)
  73.                 {
  74.                         printf("输入的数字超过8000个,程序不能处理,请重新输入\n");
  75.                         t=1;
  76.                 }
  77.         }
  78.         return t;
  79. }

  80. void string_digitArray(char *a,char *b,int *ArrayA,int *ArrayB,int *LEN_A,int *LEN_B,int *Add_Zero)
  81. {
  82.         int t,lenB,lenA,s,AddZero,i,j;
  83.         do
  84.         {
  85.                 printf("输入被除数:");
  86.                 gets(a);//-----从屏幕输入一个大数。
  87.                 t=digit_control(a);       
  88.         }
  89.         while(t==1);

  90.         do
  91.         {
  92.                 printf("输入除数:");
  93.                 gets(b);//-----从屏幕输入一个大数
  94.                 t=digit_control(b);
  95.         }
  96.         while(t==1);

  97.         lenB=count_zero(b);//求出字符串非零的实际长度。
  98.         lenA=count_zero(a);

  99.         if(lenB==0)
  100.         {
  101.                 printf("除数是零,无确定商\n");
  102.                 return ;//退出计算
  103.         }
  104.         if(lenA==0)
  105.         {
  106.                 printf("商:%d\n",0);
  107.                 printf("余数:%d\n",0);
  108.                 return ;//退出计算
  109.         }

  110.         if(lenA<lenB)
  111.         {
  112.                 printf("商:%d\n",0);
  113.                 printf("余数:%s\n",a);
  114.                 return ;//退出计算
  115.         }

  116.         s=strlen(a);//计算输入数组中的数字位数。
  117.         if(s>lenA)//说明输入的字符前面有0
  118.         {
  119.                 for(i=0;i<=lenA;i++)
  120.                    a[i]=a[i+s-lenA];//移动数字,消去前面的0
  121.         }

  122.         s=strlen(b);//计算输入数组中的数字位数。
  123.         if(s>lenB)//说明输入的字符前面有0
  124.         {
  125.                 for(i=0;i<=lenB;i++)
  126.                         b[i]=b[i+s-lenB];//移动数字,消去前面的0
  127.         }

  128.         AddZero=lenB%4;
  129.     //AddZero=1,补4个零,AddZero=2,补3个零,AddZero=3,补2个零,AddZero=0,补1个0
  130.         switch(AddZero)
  131.         {
  132.         case 3: strcat(a,"00"); strcat(b,"00");t=2;break;
  133.         case 2: strcat(a,"000"); strcat(b,"000");t=3;break;
  134.         case 1: strcat(a,"0000"); strcat(b,"0000");t=4;break;
  135.         case 0: strcat(a,"0"); strcat(b,"0");t=1;break;
  136.         }

  137.         i=strlen(a);
  138.         lenA=i/4;//计算字符数组转化为数字数组的参数。
  139.         j=i%4;
  140.         if(j==0) lenA-=1; //lenA为数组的最大下标
  141.         Vary(a,ArrayA,lenA,j);//处理字符串a为数组
  142.        
  143.         i=strlen(b);
  144.         lenB=i/4;//计算字符数组转化为数字数组的参数。
  145.         lenB-=1; //lenB为数组的最大下标
  146.         Vary(b,ArrayB,lenB,5);//处理字符串b为数组

  147.         *LEN_A=lenA;//返回被除数数组的最大下标,数组长度=数组最大下标+1;
  148.         *LEN_B=lenB;//返回除数数组的最大下标,  数组长度=数组最大下标+1;
  149.         *Add_Zero=t;//返回数组增加的零的个数。
  150.         return;
  151. }
  152. //这两个程序实际上是一个,由于太长,只好分开,分别编释。如果放在主函数中也行。
复制代码
  1. #include <stdio.h>
  2. //#include <stdlib.h>
  3. void BigDigit_DIV(int dividend[],int LENdividend, int divR[],int LENdivR,int AddZero)
  4. {
  5.   //int   dividend[];        // 被除数      dividend
  6.     int    Cdiv[2001]={0};   // 被除数镜像  copy_dividend
  7.   //int       divR[];        // 除数        divisor
  8.     int     qut[1000]={0};   // 商          quotient     
  9.     int       CTRL[7]={0};   // 控制        control
  10.   
  11.     int temp,f0,i,j,n;  

  12. void quotient_MUL_divisor(int *Cdiv,int *divR,int *CTRL);//定义内部函数,函数功能:将试商定为确定商

  13.           CTRL[0]=0;          //试商由1变为0时的判断依据。CTRL[0]=1时表示试商由1变为0
  14.     //CTRL[1]               未定义
  15.       CTRL[2]=LENdivR;    //除数数组的最大下标
  16.       CTRL[3]=0;          //每次循环参与计算的被除数起始下标         
  17.     //CTRL[4]               未定义
  18.     //CTRL[5]               临时存贮试商的值              
  19.           CTRL[6]=LENdivR+1;  //每次循环参与计算的被除数终点下标
  20.         
  21.         for(i=0;i<=LENdividend;i++)//为镜像数组赋值。i<=len(dividend[])-1
  22.                 Cdiv[i]=dividend[i];

  23.   i=0;
  24.   while(i<=LENdividend-LENdivR-1)//-----(i<=len(dividend[])-len(divR[])-1) //除法开始
  25.   {
  26.         f0=CTRL[3];
  27.         temp=(Cdiv[f0]*10000+Cdiv[f0+1])/divR[0];  // 求试商
  28.         if((temp==0)||(CTRL[0]==1))
  29.         {
  30.                 i++;//总循环次数增1
  31.                 CTRL[6]++; //被除数下标加1,被除数增加一项
  32.                 if(CTRL[6]>LENdividend)//满足条件时程序结束。------------(CTRL[6]>len(dividend[])-1)
  33.                 {
  34.                         i++;
  35.                         continue;
  36.                 }
  37.                 temp=(Cdiv[f0]*100000000+Cdiv[f0+1]*10000+Cdiv[f0+2])/divR[0]; //试商等于零,增加一项再求商。
  38.         }

  39.         CTRL[5]=temp;
  40.         quotient_MUL_divisor(Cdiv,divR,CTRL);////内部函数,将试商确定为真实商
  41.         if(CTRL[0]==1) continue;
  42.         qut[i]=CTRL[5];

  43.         j=CTRL[3];
  44.         while((Cdiv[j]==0)&&(j<=LENdividend))//计算余数从左端起非零第一项的位置下标------j<=len(dividend[])-1)
  45.                 j++;

  46.         if(j>CTRL[6])//说明本次运算余数是零,
  47.                 {
  48.                         i=i+j-CTRL[6]+CTRL[2]+1;//计算主循环下标。//......
  49.                         CTRL[3]=j;//返回被除数下标
  50.                         CTRL[6]=CTRL[3]+CTRL[2]+1;//返回被除数下标
  51.                 }

  52.                 if(j<=CTRL[6])//说明本次运算有非零的余数。
  53.                 {
  54.                         n=CTRL[6]-j+1;//求余数剩下的位数
  55.                         if(n<=CTRL[2]+1)
  56.                         {
  57.                                 temp=CTRL[2]+1-n+1;//求出要补充的新被除数个数。////。。。。
  58.                                 CTRL[3]=j;//返回被除数下标
  59.                                 CTRL[6]=CTRL[6]+temp;//返回被除数下标/////。。。
  60.                                 i=i+temp;//计算主循环下标。
  61.                         }
  62.                         else
  63.                         {
  64.                                 CTRL[3]=j;                       
  65.                         }
  66.                 }
  67.   }
  68. //===========================================================
  69.   //输出商和余数,这里本来应该从外部函数返回求出的商和余数的,这里偷懒了。
  70.         printf("商=%d",qut[0]);
  71.         for(i=1;i<LENdividend-LENdivR;i++)
  72.                 printf("%04d",qut[i]);
  73.                 printf("\n");

  74.         if(CTRL[3]>LENdividend)
  75.         {
  76.                 printf("余数=0");
  77.         }
  78.         else
  79.         {
  80.                 printf("余数=%d",Cdiv[CTRL[3]]);
  81.                 for(i=CTRL[3]+1;i<LENdividend;i++)
  82.                         printf("%04d",Cdiv[i]);
  83.                 if(AddZero!=4)
  84.                 {
  85.                 for(i=1;i<=AddZero;i++)
  86.                         Cdiv[LENdividend]/=10;
  87.                         printf("%d",Cdiv[LENdividend]);
  88.                 }
  89.         }
  90.         printf("\n");
  91. //===========================================================
  92.         return ;
  93. }


  94. void quotient_MUL_divisor(int *Cdiv,int *divR,int *CTRL)
  95. {
  96.         int i,temp=0,n;
  97.         int result[2003]={0};//----2003=len(dividend[])+3

  98.         n=CTRL[6]-CTRL[3]-CTRL[2];//对位计算。
  99.         for(i=CTRL[2];i>=0;i--)//CTRL[2]是除数数组的最大下标。
  100.                         result[i+n+CTRL[3]]=divR[i]*CTRL[5];//------------------乘法。赋给result[];

  101.         for(i=CTRL[6];i>CTRL[3];i--) //将result[]按四位一组数字进位
  102.         {
  103.                         temp=result[i]/10000;
  104.                         result[i-1]=result[i-1]+temp;
  105.                         result[i]=result[i]-temp*10000;
  106.         }
  107.                
  108.         temp=0;
  109.         for(i=CTRL[6];i>=CTRL[3];i--)
  110.         {
  111.                         Cdiv[i]=Cdiv[i]-result[i]-temp;//---------------------减法。减剩的就是余数,直接赋给Cdiv[]

  112.                         temp=0;
  113.                         if(Cdiv[i]<0)//把余数数组内的负数变为正的。
  114.                         {
  115.                                 Cdiv[i]=Cdiv[i]+10000;//////....
  116.                                 temp=1;
  117.                         }
  118.         }
  119.                 CTRL[0]=0;
  120.                
  121.         if(temp==1) /// temp==1表示余数是负的。
  122.         {
  123.                         for(i=CTRL[2];i>=0;i--)
  124.                                 Cdiv[i+n+CTRL[3]]=divR[i]+Cdiv[i+n+CTRL[3]];//-------加法,余数为负是时做一次加法
  125.                        
  126.                         for(i=CTRL[2]+CTRL[3]+n;i>CTRL[3];i--)//对相加的结果作进位处理
  127.                         {
  128.                                 temp=Cdiv[i]/10000;
  129.                                 Cdiv[i-1]=Cdiv[i-1]+temp;
  130.                                 Cdiv[i]=Cdiv[i]-temp*10000;
  131.                         }
  132.                         Cdiv[CTRL[3]]=Cdiv[CTRL[3]]-10000;

  133.                         if(CTRL[5]==1)
  134.                         {
  135.                                 CTRL[0]=1;
  136.                         }
  137.                         else
  138.                         {
  139.                                 CTRL[0]=0;
  140.                         }
  141.                         CTRL[5]=CTRL[5]-1;//余数为负时,试商减去1
  142.                 }
  143.         return ;       
  144. }
  145. //这两个程序实际上是一个,由于太长,只好分开,分别编释。如果放在主函数中也行。
复制代码


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-3-25 15:54:24 | 显示全部楼层

好帖啊!顶起来啊啊 啊啊啊啊啊啊啊啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-8-14 00:00:09 | 显示全部楼层
本帖最后由 只是呼吸 于 2015-8-14 00:13 编辑

在这一段时间里,一直对lianbch在4#所指导的方法潜水学习中,现在终于得到得到了以下的重要进展:
1)找到了vc++6.0支持的64位类型,具体而言就是UInt32x32To64(,)这个函数,这个函数出自本论坛http://bbs.emath.ac.cn/thread-216-1-1.html里6楼。
2)慢慢试着使用malloc()函数开辟空间。因一直害怕它把内存泄漏完,心存疑虑。

在有了以上的两方面知识后,这个笔算除法就可以改进了,最重要的改进是两点:
1)采用\(10^8\)进制,比上面的\(10^4\)进制效率提高了。
2)输入的数组不作特别要求,但在函数内自动将除数首位保持9个十进制数字。
   改进后的函数原型:  int Big_NumDiv_q(UINT32 *quotient,
                                                 const UINT32 * const dividend,
                                                 const UINT32 * const divisor,int LEN_dividend,int LEN_divisor);

输入参数:数组 quotient[], 用来存贮求出的商。数组的空间须事先给出。数组排列方式:数组的高位对应大的下标,数组最右边的下标是0。数组的每一位采用\(10^8\)进制。
               数组 dividend[],用来传入被除数。数组排列方式:数组的高位对应大的下标,数组最右边的下标是0。数组的每一位采用\(10^8\)进制。
               数组 divisor[],用来传入除数。数组排列方式:数组的高位对应大的下标,数组最右边的下标是0。数组的每一位采用\(10^8\)进制。
               整数 LEN_dividend,传入被除数的长度。
               整数 LEN_divisor,传入除数的长度。
运算关系:   quotient[]<-----dividend[]\(div\)divisor[]
                  quotient[]的实际长度由函数返回。
测试平台:   软件  windows XP   VC++6.0
                  硬件  AMD Athlon(tm) II X2  250   Processor   3.0GHz
                   2.00G的内存
测试结果:   10000位十进制数除以5000位十进制数。    耗时31毫秒(不计输出时间)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-8-14 00:37:31 | 显示全部楼层
声明:这个函数本人仅仅是作了初步的测试,暂时没有发现错误。
         由于程序较长,分段贴出。

       头文件:DIV.h
  1. #ifndef _MUL_H_
  2. #define _MUL_H_
  3. #include <wtypes.h>
  4. #define  BASE 100000000

  5. /*----------------------类型----------------------*/
  6. typedef unsigned int UINT32;
  7. typedef unsigned __int64 UINT64;

  8. typedef union tag_UINT64
  9. {
  10.          UINT64 u64Val;
  11.          UINT32 u32LH[2];
  12. } UInt64;
  13. /*----------------------函数----------------------*/
  14. extern int Big_NumDiv_q( UINT32 *quotient,
  15.                        const UINT32 * const dividend,
  16.                        const UINT32 * const divisor,int LEN_dividend,int LEN_divisor);////除法的求商函数。

  17. extern void DIV_DigitFomart(const UINT32 * const dividend,int LEN_dividend,const UINT32 * const divisor,
  18.                                                         int LEN_divisor,int *Cdiv,int *divR);/////除法之前的格式化


  19. extern void Big_Digit_DIV(UINT32 *qut,int *Work, int *Cdiv,int LENdividend, int *divR,int LENdivR);

  20. extern void quotient_MUL_divisor(int *Work,int *Cdiv,int *divR,int *CTRL);

  21. #endif
复制代码



毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-8-14 00:47:46 | 显示全部楼层
原型函数:int Big_NumDiv_q.c
             主函数首先调用的函数。

函数原型:  int Big_NumDiv_q(UINT32 *quotient,
                                                 const UINT32 * const dividend,
                                                 const UINT32 * const divisor,int LEN_dividend,int LEN_divisor);

输入参数:数组 quotient[], 用来存贮求出的商。数组的空间须事先给出。数组排列方式:数组的高位对应大的下标,数组最右边的下标是0。数组的每一位采用\(10^8\)进制。
               数组 dividend[],用来传入被除数。数组排列方式:数组的高位对应大的下标,数组最右边的下标是0。数组的每一位采用\(10^8\)进制。
               数组 divisor[],用来传入除数。数组排列方式:数组的高位对应大的下标,数组最右边的下标是0。数组的每一位采用\(10^8\)进制。
               整数 LEN_dividend,传入被除数的长度。
               整数 LEN_divisor,传入除数的长度。
运算关系:   quotient[]<-----dividend[]\(\div\)divisor[]
                  quotient[]的实际长度由函数返回。



  1. #include "DIV.h"
  2. #include "stdio.h"

  3. int Big_NumDiv_q( UINT32 *quotient,
  4.                        const UINT32 * const dividend,
  5.                        const UINT32 * const divisor,int LEN_dividend,int LEN_divisor)////除法的求余函数。
  6. {
  7.         int i,N,M;
  8.         int *Cdiv,*divR,*Work;

  9.         if((LEN_divisor==1)&&(divisor[0]==0))///若除数为零,
  10.         {
  11.                 printf("err:divisor is zeor\n");///显示出错信息。
  12.                 return 0;
  13.         }

  14.         if(LEN_dividend<LEN_divisor)///若被除数小于除数,
  15.         {
  16.                 remainder[0]=0; ///商为零,
  17.                 return 0;
  18.         }

  19.         if((LEN_dividend==1)&&(dividend[0]==0))///若被除数为零,
  20.         {
  21.                 remainder[0]=0; ///商为零。
  22.                 return 0;
  23.         }
  24. //-----------------------------------------------以上语句对除法进行预处理。--------------------------//

  25.                 N=LEN_dividend+4;///--------------------增加长度。为存贮格式化后的新被除数作准备。N-1是数组上限。
  26.                 M=LEN_divisor+2;///---------------------增加长度,为存贮格式化后的新除数作准备。M-1是数组的上限。
  27.                 if((Cdiv= (int *)malloc(N * (sizeof(UINT32))))==NULL)  //调用库函数,开辟内存,用于存贮格式化了的被除数
  28.                 {
  29.                         printf("fail\n");
  30.                         exit(0);
  31.                 }

  32.                 if((divR= (int *)malloc(M * (sizeof(UINT32))))==NULL)  //调用库函数,开辟内存,用于存贮格式化了的除数。
  33.                 {
  34.                         printf("fail\n");
  35.                         exit(0);
  36.                 }/////

  37.                 if((Work= (int *)malloc(N * (sizeof(UINT32))))==NULL)  //调用库函数,开辟内存,工作数组。
  38.                 {
  39.                         printf("fail\n");
  40.                         exit(0);
  41.                 }
  42.      
  43.                 N--;
  44.                 M--;
  45.                 for(i=N;i>=0;i--)
  46.                 {
  47.                         Cdiv[i]=0;////把生成的数组初始化为0;
  48.                         Work[i]=0;
  49.                 }

  50.                 for(i=M;i>=0;i--)
  51.                 {
  52.                         divR[i]=0;////把生成的数组初始化为0;       
  53.                 }


  54.         DIV_DigitFomart(dividend,LEN_dividend,divisor,LEN_divisor,Cdiv,divR);////调用除法格式化函数。将被除数和除数格式化。

  55.                 while((Cdiv[N]==0)&&(N>=0))//寻找被除数最高位下标。
  56.                 {
  57.                         N--;
  58.                 }

  59.                 while((divR[M]==0)&&(M>=0))//寻找除数最高位下标。
  60.                 {
  61.                         M--;
  62.                 }

  63.         Big_Digit_DIV(quotient,Work,Cdiv,N,divR,M);//调用除法函数做除法。

  64.                 free(Cdiv);////释放内存。
  65.                         Cdiv=NULL;
  66.                 free(divR);
  67.                         divR=NULL;////
  68.                 free(Work);
  69.                         Work=NULL;////

  70.                 i=LEN_dividend-LEN_divisor;
  71.                 while((quotient[i]==0)&&(i>=0))//寻找求出的商的最高位下标。
  72.                 {
  73.                         i--;
  74.                 }

  75.                 if(i<0)
  76.                 {
  77.                         return 0;
  78.                 }       
  79.                 return i;       
  80. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 19:27 , Processed in 0.185715 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表