笔算除法的代码

只是呼吸 · 发表于 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的容量）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <windows.h>
int main()
{
int dividend[2000]={0}; // 被除数 dividend
int Cdiv[2000]={0}; // 被除数镜像 copy_dividend
int divR[1000]={0}; // 除数 divisor
int result[1002]={0}; // 乘积的结果 result
int qut[999]={0}; // 商 quotient
int CTRL[12]={0}; // 控制 control
int t1,t2; // 时间 time
unsigned int seed; // 初始化随机函数的发生器
int temp,f0,i;
void control_neno(int *Cdiv,int *qut,int *CTRL);
void quotient_MUL_divisor(int *result,int *divR,int *CTRL);
void dividend_SUB_result(int *Cdiv,int *result,int *divR,int *CTRL);
void OUT_text(int *dividend,int *divR,int *qut,int *Cdiv,int *CTRL);
void ArraysFormat();
seed=time(0);//=======以下部分用来随机产生两个大数。代替 ArraysFormat();
srand(seed);
Cdiv[0]=3141; //------------共产生8000位十进制数，作为被除数。存入数组Cdiv[]中。
dividend[0]=3141;
for(i = 1; i<2000; i++)
{
Cdiv[i]=(rand())%10000;
dividend[i]=Cdiv[i];
}
divR[0]=27182; //------------共产生4001位十进制数。作为除数。存入数组divR[]中。
for(i = 1; i<1000; i++)
divR[i]=(rand())%10000;
t1=GetTickCount();//时间计时开始；
CTRL[0]=0; //试商由1变为0时的判断依据。CTRL[0]=1时表示试商由1变为0
CTRL[1]=1000; //除数的个数。
CTRL[2]=CTRL[1]-1; //除数数组的最大下标。
//CTRL[3] 未定义。
//CTRL[4] 总的循环控制变量。
//CTRL[5] 余数的符号
//CTRL[6] 每次循环参与计算的被除数起始位下标。
//CTRL[7] 试商的值。
//CTRL[8] 余数从左端起非零第一项的位置。
//CTRL[9] 每次循环参与计算的被除数个数。
CTRL[10]=1001; //余数剩下的位数。
ArraysFormat();
while(CTRL[4]<=999) //-----(CTRL[4]<=len(Cdiv[])-len(divR[])-1)
{
f0=CTRL[6];
CTRL[9]=1001;
temp=(Cdiv[f0]*10000+Cdiv[f0+1])/divR[0]; // 求试商
if((temp==0)||((temp==1)&&(CTRL[0]==1)))
{
if(CTRL[10]<CTRL[1]+1)
{
qut[CTRL[4]]=0;
CTRL[4]++;
}
CTRL[9]++;
temp=(Cdiv[f0]*100000000+Cdiv[f0+1]*10000+Cdiv[f0+2])/divR[0]; //试商等于零，增加一项再求商。
}
CTRL[7]=temp;
quotient_MUL_divisor(result,divR,CTRL);////乘法函数
dividend_SUB_result(Cdiv,result,divR,CTRL);////减法函数
if(CTRL[5]>=0)
{
qut[CTRL[4]]=temp;
CTRL[0]=0;
}
else
{
qut[CTRL[4]]=temp-1;
if(temp==1)
{
CTRL[0]=1;
}
else
{
CTRL[0]=0;
}
}
CTRL[4]++;
control_neno(Cdiv,qut,CTRL);//商0的函数
}
t2=GetTickCount();//时间计时结束。
OUT_text(dividend,divR,qut,Cdiv,CTRL);//输出函数
printf("被除数已输出到e盘的dividend.txt 文件中。\n");
printf("除数已输出到e盘的divisor.txt 文件中。\n");
printf("商已输出到e盘的quotient.txt 文件中。\n");
printf("余数已输出到e盘的remainder.txt 文件中。\n");
printf("时间%d ms\n",t2-t1);
return 0;
}
void quotient_MUL_divisor(int *result,int *divR,int *CTRL)
{
int i,temp=0,n;
n=CTRL[9]-CTRL[1];
result[0]=0;
result[1]=0;
for(i=CTRL[2];i>=0;i--)
result[i+n]=divR[i]*CTRL[7];
for(i=CTRL[2]+n;i>=1;i--)
{
temp=result[i]/10000;
result[i-1]=result[i-1]+temp;
result[i]=result[i]-temp*10000;
}
return ;
}
void dividend_SUB_result(int *Cdiv,int *result,int *divR,int *CTRL)
{
int i,temp=0,n,j;
int carry[1002]={0};
n=CTRL[9]-CTRL[1];
for(i=CTRL[2]+n;i>=0;i--)
{
carry[i]=Cdiv[i+CTRL[6]]-result[i]-temp;
temp=0;
if(carry[i]<0)
{
carry[i]=carry[i]+10000;
temp=1;
}
}
CTRL[5]=1;
if(temp==1)
{
for(i=CTRL[2];i>=0;i--)
carry[i+n]=divR[i]+carry[i+n];
for(i=CTRL[2]+n;i>=1;i--)
{
temp=carry[i]/10000;
carry[i-1]=carry[i-1]+temp;
carry[i]=carry[i]-temp*10000;
}
carry[0]=carry[0]-10000;
CTRL[5]=-1;
}
for(i=0;i<=CTRL[2]+n;i++)
Cdiv[i+CTRL[6]]=carry[i];
j=0; //计算余数从左端起非零第一项的位置。
while((carry[j]==0) && (j<=CTRL[2]+n))
j++;
CTRL[6]=CTRL[6]+j;
CTRL[8]=j;
CTRL[10]=CTRL[1]+n-j;
return ;
}
void control_neno(int *Cdiv,int *qut,int *CTRL)
{
int i,j,m,s;
if(CTRL[10]>0)
{
m=CTRL[1]-CTRL[10];
for(i=m;i>=1;i--)
{
qut[CTRL[4]]=0;
CTRL[4]++;
}
}
if(CTRL[10]==0)
{
s=0;//计算j 的个数。
j=CTRL[6]-CTRL[8]+CTRL[9];
while(Cdiv[j]==0)
{
j++;
s++;
}
CTRL[6]=j;
m=s+CTRL[1];
for(i=1;i<=m;i++)
{
qut[CTRL[4]]=0;
CTRL[4]++;
}
}
return ;
}
void OUT_text(int *dividend,int *divR,int *qut,int *Cdiv,int *CTRL)
{
int i;
FILE *fp; // 输出数据到文件
if((fp=fopen("e:\\dividend.txt","w"))==NULL)
{
printf("not open dividend.txt");
exit(0);
}
for(i=0;i<2000;i++)
fprintf(fp,"%04d",dividend[i]);//输出被除数。
if((fp=fopen("e:\\divisor.txt","w"))==NULL)
{
printf("not open divisor.txt");
exit(0);
}
for(i=0;i<1000;i++)
fprintf(fp,"%04d",divR[i]);//输出除数。
if((fp=fopen("e:\\quotient.txt","w"))==NULL)
{
printf("not open quotient.txt");
exit(0);
}
for(i=0;i<1000;i++)
fprintf(fp,"%04d",qut[i]);//输出商。
if((fp=fopen("e:\\remainder.txt","w"))==NULL)
{
printf("not open remainder.txt");
exit(0);
}
for(i=CTRL[6];i<2000;i++)
fprintf(fp,"%04d",Cdiv[i]);//输出余数。
fclose(fp);
return ;
}
void ArraysFormat()
{
//这个函数将键盘、文件输入的数字字符串转化为数字，存入数组中，
//每个存贮单元中存入四位十进制数。
//除数的第一位（最高位）需确保五位十进制数。
}

复制代码

gxqcn · 发表于 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写的除法----------方法是“循环相减”求商，这样很慢，但能保证结果是正确的----------求出商来对照。用眼睛一行一行的扫，还未发现错误。

liangbch · 发表于 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”，要把输出余数的语句改一改才行。

if(CTRL[6]<2000)
{
for(i=CTRL[6];i<2000;i++)
fprintf(fp,"%04d",Cdiv[i]);//输出余数。
}
else
{
fprintf(fp,"%d",0);//输出余数。
}

复制代码

把输出余数的语句改成这样就可以了。

只是呼吸 · 发表于 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，采用分别编译的方式，给出商和余数。

#include <stdio.h>
#include <string.h>
int main()
{
extern void BigDigit_DIV(int *dividend,int LENdividend, int *divR,int LENdivR,int AddZero); //外部函数，函数功能：将两个数相除得到结果
void string_digitArray(char *a,char *b,int *ArrayA,int *ArrayB,int *LEN_A,int *LEN_B,int *Add_Zero);//内部函数，函数功能：将两个字符串转化为数组
int digit_control(char a[]); //内部函数，函数功能：控制数字规模
int count_zero(char b[]); //内部函数，函数功能：统计0的个数
void Vary(char a[],int pr[],int AddZero); //内部函数，函数功能：转化字符串为数组
int ArrayA[2010]={0}; //被除数
int ArrayB[2010]={0}; //除数
int quotient[2010]={0}; //商
//int rm[2010]={0}; //余数
int LEN_ArrayA,LEN_ArrayB,AddZero;
int *LEN_A,*LEN_B,*Add_Zero;
char a[10010];
char b[10010];
LEN_A=&LEN_ArrayA;
LEN_B=&LEN_ArrayB;
Add_Zero=&AddZero;
string_digitArray(a,b,ArrayA,ArrayB,LEN_A,LEN_B,Add_Zero);//把字符串a,b,转化为数字数组ArrayA,ArrayB，并返回数组的最大下标，每个元素中存4个十进制数字。
BigDigit_DIV(ArrayA,LEN_ArrayA,ArrayB,LEN_ArrayB,AddZero);
return 0;
}
void Vary(char dm[],int kk[],int ss,int yy) //转化字符串A为数组存入kk[]中
{
int r,s,kd;
r=0;
if (yy==0)
{
for(s=0;s<=ss;s++,r+=4)
kk[s]=dm[r]*1000+dm[r+1]*100+dm[r+2]*10+dm[r+3]-53328;
}
else
{
for (kd=0;kd<=yy-2;kd++)
{
kk[0]+=dm[kd]-48;
kk[0]*=10;
}
kk[0]+=dm[yy-1]-48;
for(s=1;s<=ss;s++,yy+=4)
kk[s]=dm[yy]*1000+dm[yy+1]*100+dm[yy+2]*10+dm[yy+3]-53328;
}
}
int count_zero(char b[])
{
int j,s;
j=strlen(b);
s=0;
while(b[s]=='0')//找出除数中第一个非零的数的位置
s++;
j=j-s;//求出非零的实际长度。
return j;
}
int digit_control(char a[])
{
int t,i,s,lenA;
i=strlen(a);//计算输入数组中的数字位数。
for(s=0;s<i;s++)
{
if(isdigit(a[s])==0)
{
printf("输入的符号中有数字以外的其它字符，请重新输入\n");
t=1;
break;
}
}
if(t!=1)
{
lenA=count_zero(a);//求出非零位数
if(lenA>8000)
{
printf("输入的数字超过8000个，程序不能处理，请重新输入\n");
t=1;
}
}
return t;
}
void string_digitArray(char *a,char *b,int *ArrayA,int *ArrayB,int *LEN_A,int *LEN_B,int *Add_Zero)
{
int t,lenB,lenA,s,AddZero,i,j;
do
{
printf("输入被除数：");
gets(a);//-----从屏幕输入一个大数。
t=digit_control(a);
}
while(t==1);
do
{
printf("输入除数：");
gets(b);//-----从屏幕输入一个大数
t=digit_control(b);
}
while(t==1);
lenB=count_zero(b);//求出字符串非零的实际长度。
lenA=count_zero(a);
if(lenB==0)
{
printf("除数是零，无确定商\n");
return ;//退出计算
}
if(lenA==0)
{
printf("商：%d\n",0);
printf("余数：%d\n",0);
return ;//退出计算
}
if(lenA<lenB)
{
printf("商：%d\n",0);
printf("余数：%s\n",a);
return ;//退出计算
}
s=strlen(a);//计算输入数组中的数字位数。
if(s>lenA)//说明输入的字符前面有0
{
for(i=0;i<=lenA;i++)
a[i]=a[i+s-lenA];//移动数字，消去前面的0
}
s=strlen(b);//计算输入数组中的数字位数。
if(s>lenB)//说明输入的字符前面有0
{
for(i=0;i<=lenB;i++)
b[i]=b[i+s-lenB];//移动数字，消去前面的0
}
AddZero=lenB%4;
//AddZero=1,补4个零，AddZero=2,补3个零，AddZero=3,补2个零，AddZero=0，补1个0
switch(AddZero)
{
case 3: strcat(a,"00"); strcat(b,"00");t=2;break;
case 2: strcat(a,"000"); strcat(b,"000");t=3;break;
case 1: strcat(a,"0000"); strcat(b,"0000");t=4;break;
case 0: strcat(a,"0"); strcat(b,"0");t=1;break;
}
i=strlen(a);
lenA=i/4;//计算字符数组转化为数字数组的参数。
j=i%4;
if(j==0) lenA-=1; //lenA为数组的最大下标
Vary(a,ArrayA,lenA,j);//处理字符串a为数组
i=strlen(b);
lenB=i/4;//计算字符数组转化为数字数组的参数。
lenB-=1; //lenB为数组的最大下标
Vary(b,ArrayB,lenB,5);//处理字符串b为数组
*LEN_A=lenA;//返回被除数数组的最大下标，数组长度=数组最大下标+1；
*LEN_B=lenB;//返回除数数组的最大下标，数组长度=数组最大下标+1；
*Add_Zero=t;//返回数组增加的零的个数。
return;
}
//这两个程序实际上是一个，由于太长，只好分开，分别编释。如果放在主函数中也行。

复制代码

#include <stdio.h>
//#include <stdlib.h>
void BigDigit_DIV(int dividend[],int LENdividend, int divR[],int LENdivR,int AddZero)
{
//int dividend[]; // 被除数 dividend
int Cdiv[2001]={0}; // 被除数镜像 copy_dividend
//int divR[]; // 除数 divisor
int qut[1000]={0}; // 商 quotient
int CTRL[7]={0}; // 控制 control
int temp,f0,i,j,n;
void quotient_MUL_divisor(int *Cdiv,int *divR,int *CTRL);//定义内部函数，函数功能：将试商定为确定商
CTRL[0]=0; //试商由1变为0时的判断依据。CTRL[0]=1时表示试商由1变为0
//CTRL[1] 未定义
CTRL[2]=LENdivR; //除数数组的最大下标
CTRL[3]=0; //每次循环参与计算的被除数起始下标
//CTRL[4] 未定义
//CTRL[5] 临时存贮试商的值
CTRL[6]=LENdivR+1; //每次循环参与计算的被除数终点下标
for(i=0;i<=LENdividend;i++)//为镜像数组赋值。i<=len(dividend[])-1
Cdiv[i]=dividend[i];
i=0;
while(i<=LENdividend-LENdivR-1)//-----(i<=len(dividend[])-len(divR[])-1) //除法开始
{
f0=CTRL[3];
temp=(Cdiv[f0]*10000+Cdiv[f0+1])/divR[0]; // 求试商
if((temp==0)||(CTRL[0]==1))
{
i++;//总循环次数增1
CTRL[6]++; //被除数下标加1，被除数增加一项
if(CTRL[6]>LENdividend)//满足条件时程序结束。------------(CTRL[6]>len(dividend[])-1)
{
i++;
continue;
}
temp=(Cdiv[f0]*100000000+Cdiv[f0+1]*10000+Cdiv[f0+2])/divR[0]; //试商等于零，增加一项再求商。
}
CTRL[5]=temp;
quotient_MUL_divisor(Cdiv,divR,CTRL);////内部函数，将试商确定为真实商
if(CTRL[0]==1) continue;
qut[i]=CTRL[5];
j=CTRL[3];
while((Cdiv[j]==0)&&(j<=LENdividend))//计算余数从左端起非零第一项的位置下标------j<=len(dividend[])-1)
j++;
if(j>CTRL[6])//说明本次运算余数是零，
{
i=i+j-CTRL[6]+CTRL[2]+1;//计算主循环下标。//......
CTRL[3]=j;//返回被除数下标
CTRL[6]=CTRL[3]+CTRL[2]+1;//返回被除数下标
}
if(j<=CTRL[6])//说明本次运算有非零的余数。
{
n=CTRL[6]-j+1;//求余数剩下的位数
if(n<=CTRL[2]+1)
{
temp=CTRL[2]+1-n+1;//求出要补充的新被除数个数。////。。。。
CTRL[3]=j;//返回被除数下标
CTRL[6]=CTRL[6]+temp;//返回被除数下标/////。。。
i=i+temp;//计算主循环下标。
}
else
{
CTRL[3]=j;
}
}
}
//===========================================================
//输出商和余数,这里本来应该从外部函数返回求出的商和余数的，这里偷懒了。
printf("商=%d",qut[0]);
for(i=1;i<LENdividend-LENdivR;i++)
printf("%04d",qut[i]);
printf("\n");
if(CTRL[3]>LENdividend)
{
printf("余数=0");
}
else
{
printf("余数=%d",Cdiv[CTRL[3]]);
for(i=CTRL[3]+1;i<LENdividend;i++)
printf("%04d",Cdiv[i]);
if(AddZero!=4)
{
for(i=1;i<=AddZero;i++)
Cdiv[LENdividend]/=10;
printf("%d",Cdiv[LENdividend]);
}
}
printf("\n");
//===========================================================
return ;
}
void quotient_MUL_divisor(int *Cdiv,int *divR,int *CTRL)
{
int i,temp=0,n;
int result[2003]={0};//----2003=len(dividend[])+3
n=CTRL[6]-CTRL[3]-CTRL[2];//对位计算。
for(i=CTRL[2];i>=0;i--)//CTRL[2]是除数数组的最大下标。
result[i+n+CTRL[3]]=divR[i]*CTRL[5];//------------------乘法。赋给result[];
for(i=CTRL[6];i>CTRL[3];i--) //将result[]按四位一组数字进位
{
temp=result[i]/10000;
result[i-1]=result[i-1]+temp;
result[i]=result[i]-temp*10000;
}
temp=0;
for(i=CTRL[6];i>=CTRL[3];i--)
{
Cdiv[i]=Cdiv[i]-result[i]-temp;//---------------------减法。减剩的就是余数，直接赋给Cdiv[]
temp=0;
if(Cdiv[i]<0)//把余数数组内的负数变为正的。
{
Cdiv[i]=Cdiv[i]+10000;//////....
temp=1;
}
}
CTRL[0]=0;
if(temp==1) /// temp==1表示余数是负的。
{
for(i=CTRL[2];i>=0;i--)
Cdiv[i+n+CTRL[3]]=divR[i]+Cdiv[i+n+CTRL[3]];//-------加法,余数为负是时做一次加法
for(i=CTRL[2]+CTRL[3]+n;i>CTRL[3];i--)//对相加的结果作进位处理
{
temp=Cdiv[i]/10000;
Cdiv[i-1]=Cdiv[i-1]+temp;
Cdiv[i]=Cdiv[i]-temp*10000;
}
Cdiv[CTRL[3]]=Cdiv[CTRL[3]]-10000;
if(CTRL[5]==1)
{
CTRL[0]=1;
}
else
{
CTRL[0]=0;
}
CTRL[5]=CTRL[5]-1;//余数为负时，试商减去1
}
return ;
}
//这两个程序实际上是一个，由于太长，只好分开，分别编释。如果放在主函数中也行。

复制代码

neluzyy1 · 发表于 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

#ifndef _MUL_H_
#define _MUL_H_
#include <wtypes.h>
#define BASE 100000000
/*----------------------类型----------------------*/
typedef unsigned int UINT32;
typedef unsigned __int64 UINT64;
typedef union tag_UINT64
{
UINT64 u64Val;
UINT32 u32LH[2];
} UInt64;
/*----------------------函数----------------------*/
extern int Big_NumDiv_q( UINT32 *quotient,
const UINT32 * const dividend,
const UINT32 * const divisor,int LEN_dividend,int LEN_divisor);////除法的求商函数。
extern void DIV_DigitFomart(const UINT32 * const dividend,int LEN_dividend,const UINT32 * const divisor,
int LEN_divisor,int *Cdiv,int *divR);/////除法之前的格式化
extern void Big_Digit_DIV(UINT32 *qut,int *Work, int *Cdiv,int LENdividend, int *divR,int LENdivR);
extern void quotient_MUL_divisor(int *Work,int *Cdiv,int *divR,int *CTRL);
#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[]的实际长度由函数返回。

#include "DIV.h"
#include "stdio.h"
int Big_NumDiv_q( UINT32 *quotient,
const UINT32 * const dividend,
const UINT32 * const divisor,int LEN_dividend,int LEN_divisor)////除法的求余函数。
{
int i,N,M;
int *Cdiv,*divR,*Work;
if((LEN_divisor==1)&&(divisor[0]==0))///若除数为零，
{
printf("err:divisor is zeor\n");///显示出错信息。
return 0;
}
if(LEN_dividend<LEN_divisor)///若被除数小于除数，
{
remainder[0]=0; ///商为零，
return 0;
}
if((LEN_dividend==1)&&(dividend[0]==0))///若被除数为零，
{
remainder[0]=0; ///商为零。
return 0;
}
//-----------------------------------------------以上语句对除法进行预处理。--------------------------//
N=LEN_dividend+4;///--------------------增加长度。为存贮格式化后的新被除数作准备。N-1是数组上限。
M=LEN_divisor+2;///---------------------增加长度，为存贮格式化后的新除数作准备。M-1是数组的上限。
if((Cdiv= (int *)malloc(N * (sizeof(UINT32))))==NULL) //调用库函数，开辟内存，用于存贮格式化了的被除数
{
printf("fail\n");
exit(0);
}
if((divR= (int *)malloc(M * (sizeof(UINT32))))==NULL) //调用库函数，开辟内存，用于存贮格式化了的除数。
{
printf("fail\n");
exit(0);
}/////
if((Work= (int *)malloc(N * (sizeof(UINT32))))==NULL) //调用库函数，开辟内存，工作数组。
{
printf("fail\n");
exit(0);
}
N--;
M--;
for(i=N;i>=0;i--)
{
Cdiv[i]=0;////把生成的数组初始化为0；
Work[i]=0;
}
for(i=M;i>=0;i--)
{
divR[i]=0;////把生成的数组初始化为0；
}
DIV_DigitFomart(dividend,LEN_dividend,divisor,LEN_divisor,Cdiv,divR);////调用除法格式化函数。将被除数和除数格式化。
while((Cdiv[N]==0)&&(N>=0))//寻找被除数最高位下标。
{
N--;
}
while((divR[M]==0)&&(M>=0))//寻找除数最高位下标。
{
M--;
}
Big_Digit_DIV(quotient,Work,Cdiv,N,divR,M);//调用除法函数做除法。
free(Cdiv);////释放内存。
Cdiv=NULL;
free(divR);
divR=NULL;////
free(Work);
Work=NULL;////
i=LEN_dividend-LEN_divisor;
while((quotient[i]==0)&&(i>=0))//寻找求出的商的最高位下标。
{
i--;
}
if(i<0)
{
return 0;
}
return i;
}

复制代码

账号		自动登录	找回密码
密码			欢迎注册

[原创] 笔算除法的代码

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