最优除法步骤试验（附源代码）

只是呼吸 · 发表于 2024-1-5 12:32:13

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

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

×

   在写大整数的除法过程中，包括本人在内的很多人，因为没有掌握除法的内在联系，走了弯路。
   本人用的除法采用的是\(10^8\)进制，最近在扩展到\(10^9\)进制的过程中，就遇到了困难。心想：难道一个进制就要单独写一个除法程序吗？
重新思考后，发现大整数的加法、减法、乘法（硬乘）都有一个共同的特征规律：

1）输入数据能采用任意\(10^k\)进制，运算结果不受影响（因为计算机字长限制以及编译器不支持的进制除外）。
2）运算过程中不需要改变输入数据的结构和大小
   结合加法、减法、乘法（硬乘）的共同特征规律，我们有理由认为，除法的运算规律也应当如此。
   当我们按照上面两个特征规律，结合“笔算除法的最优估商”，写出笔算除法程序时，我们不但得到了商，还同时得到了余数，这个余数是笔算除法的必然结果。
各位爱好者可以查看一下自己写的除法程序，如果余数不是自然得到，而是要添加一些步骤才得到，那么一定是运算过程中“改变了输入数据的结构和大小”。
下面是测试源代码。
说明：源代码做在一个文件中，在debug 模式下编译通过。

只是呼吸 · 发表于 2024-1-5 12:35:22

#include <stdio.h>
#include <time.h>
#include <string.h>
#include <wtypes.h>
/* 变量长度 */
typedef unsigned int UINT32; /* 定义三十二位无符号变量 */
typedef unsigned __int64 UINT64; /* 定义六十四位无符号变量 */
/* 一些宏定义 */
#define BASE 1000000 /* 大数的基数（10^k进制，可修改）*/
#define BASE_EXP 6 /* 基数的指数 k，与基数同时修改 */
#define DIVID 3000 /* 被除数的数字个数（可修改）*/
#define DIVIS 2000 /* 除数的数字个数（可修改）*/
/* 函数声明，除法函数 */
int DivAbs( UINT32 *dividend, UINT32 *divisor,
UINT32 *quotient,UINT32 *remainder,int *CtrL);
int DivHelp(UINT32 *Wdiv, UINT32 *divisor, UINT32 *qut, int *CtrL);
int MulSubAdd(UINT32 *Wdiv, UINT32 *divisor, int *CtrL);
/* 函数声明，辅助函数 */
int _Output(UINT32 *quotient, UINT32 *remainder, int *CtrL);
int _Input(UINT32 *dividend, UINT32 *divisor, int *CtrL);
void _RandomNumbers(char *a, int lenA);
int _StringToDigit(UINT32 *result, char *str);
/* 函数声明，结果检测（非必须） */
int _resultTest(UINT32 *dividend,UINT32 *divisor,UINT32 *quotient,UINT32 *remainder,int *CtrL);
/* 全局变量 */
static char a[DIVID+2]={0}; /* 被除数a */
static char b[DIVIS+2]={0}; /* 除数b */
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
UINT32 dividend[DIVID/BASE_EXP+3]={0}; //dividend 被除数
UINT32 divisor[DIVIS/BASE_EXP+3]={0}; //divisor 除数
UINT32 quotient[DIVID/BASE_EXP-DIVIS/BASE_EXP+5]={0}; //quotient 商
UINT32 remainder[DIVIS/BASE_EXP+7]={0}; //remainder 余数
int CtrL[10]={0};
//CtrL , 控制数组，代替结构体传送必须的各个参数
//CtrL[0]=dividendLEN 传送被除数（数组）的长度
//CtrL[1]=divisorLEN 传送除数（数组）的长度
//CtrL[2]=quotientLEN 传送商（数组）的长度
//CtrL[3]=remainderLEN 传送余数（数组）的长度
_Input(dividend,divisor,CtrL);
DivAbs(dividend,divisor,quotient,remainder,CtrL);//// 绝对值除法，求商和余数
_Output(quotient,remainder,CtrL);
_resultTest(dividend,divisor,quotient,remainder,CtrL);
return 0;
}
int DivAbs( UINT32 *dividend, UINT32 *divisor,UINT32 *quotient,UINT32 *remainder,int *CtrL)////除法开始。
{
//数组采用10^k进制，数组的高位对应较大的下标，数组的低位对应较小的下标
//CtrL[0]=dividendLEN 传送被除数（数组）的长度
//CtrL[1]=divisorLEN 传送除数（数组）的长度
//CtrL[2]=quotientLEN 传送商（数组）的长度
//CtrL[3]=remainderLEN 传送余数（数组）的长度
int dividendLEN=CtrL[0];
int divisorLEN=CtrL[1];
int remainderLEN=0;
int i;
i=BASE_EXP;
remainderLEN=1;////临时借用变量remainderLEN
do
{
remainderLEN*=10;
i--;
}while(i>0);
if (remainderLEN !=BASE)
{
printf("您输入的 BASE 的零的个数和指数 BASE_EXP 不相等\n");
exit(1);
}
if ( BASE>1000000)
{
printf("大整数的基数超过10^6，超过计算机的字长，本程序不涉及，请输入的大整数基数<=10^6");
exit(1);
}
if ( divisorLEN==1)
{
printf("除数为一个limb，属于多精度除以单精度的情况，本程序不涉及。");
exit(1);
}
if (divisorLEN == 0)///若除数为零，
{
printf("err:divisor is zeor\n");
exit(1);
}
if ((dividendLEN == 0) || (dividendLEN < divisorLEN))///若被除数为零，或被除数小于除数，
{
printf("%d",0);
exit(1);
}
for(i=0; i<dividendLEN; i++)//拷贝
{
remainder[i]=dividend[i];////// remainder[]是被除数的拷贝，既是工作数组，又得到余数
}
remainderLEN=dividendLEN;
DivHelp(remainder,divisor,quotient,CtrL);//除法
i = DIVIS/BASE_EXP+6;
while ((remainder[i] == 0) && (i >= 0)) /// 计算余数长度
{
i--;
}
CtrL[3]=i+1;
i = dividendLEN-divisorLEN;
while ((quotient[i] == 0) && (i >= 0)) /// 计算商的长度
{
i--;
}
CtrL[2]=i+1;
return 0;
}
int DivHelp(UINT32 *Wdiv, UINT32 *divisor, UINT32 *qut, int *CtrL)
{
// Wdiv[]; 被除数的工作数组，同时也是余数数组
// qut[]; 商
//CtrL[0] 传送被除数（数组）的长度
//CtrL[1] 传送除数（数组）的长度
//CtrL[4] 试商由一确定为零时的判断依据
//CtrL[5] 随时刷新的被除数最高位下标(用于除法对位),
//CtrL[6] 传送试商的值
//CtrL[8] 对位计算
// UINT32 TempArray[DIVIS/BASE_EXP+5] = { 0 };///存储试商与除数相乘所得的结果
UINT64 D = 0;
UINT64 C = 0;
int divisorMaxLable=CtrL[1]-1; // 除数数组的最大下标
int changeLable=CtrL[0]-1; // 随时刷新的被除数起始下标，初值 CtrL[0]-1
int i;
CtrL[4] = 0;
CtrL[5]=CtrL[0]-1; //随时刷新的被除数起始下标，初值 CtrL[0]-1 做首次计算
CtrL[8] = 0;
i = changeLable - divisorMaxLable; //除法总的循环次数的初始值（从ctrl[0]-ctrl[0] 开始计数）
D = UInt32x32To64(divisor[divisorMaxLable], BASE) +(UINT64)divisor[divisorMaxLable - 1];
while (i >= 0)//-----//除法开始
{
C = UInt32x32To64(Wdiv[changeLable], BASE) + (UINT64)Wdiv[changeLable - 1];////-----C=Wdiv[f0]*10^8+Wdiv[f0-1].
if ((C < D) || (CtrL[4] == 1))
{
i--;
if(i<0)
{
continue;
}
C *= BASE;
C += (UINT64)Wdiv[changeLable - 2];//C=Wdiv[f0]*10^2k+Wdiv[f0-1]*10^k+Wdiv[f0-2]
// three_div_two(Wdiv, divisor,CtrL);
CtrL[8] = 1;
}
CtrL[6] = (int)(C / D); /// 求试商
MulSubAdd(Wdiv,divisor,CtrL); /// 被除数-商*除数
if(CtrL[4]==1)continue;
qut[i] = CtrL[6]; ////已定商，赋值给数组
while ((Wdiv[changeLable] == 0) && (changeLable >= 0)) /// 刷新被除数最高位下标changeLable,用于下一次计算
{
changeLable--;
}
i = changeLable - divisorMaxLable;
CtrL[5]=changeLable;
CtrL[8] = 0;
}
}///*/////
int MulSubAdd(UINT32 *Wdiv,UINT32 *divisor,int *CtrL)
{
//CtrL[1] 传送除数（数组）的长度
//CtrL[5] 随时刷新的被除数最高位下标(用于除法对位),
//CtrL[6] 传送试商的值
//CtrL[8] 对位计算
UINT32 TempArray[DIVIS/BASE_EXP+7] = { 0 };///临时存储试商与除数相乘所得的结果
int divisorMaxLable=CtrL[1]-1; ///除数数组的最大下标
int temp,MM;
int i;
UINT64 C=0,D=0;
temp = 0;
TempArray[divisorMaxLable+1] = 0;
TempArray[divisorMaxLable+2] = 0;
for (i= 0; i <= divisorMaxLable; i++)
{
C = UInt32x32To64(divisor[i], CtrL[6]) + temp;/// 乘法。 CtrL[6]是函数传入的试商。C=商*除数;
temp = (int)(C / BASE);
TempArray[i] = (int)(C - UInt32x32To64(temp, BASE));
}
TempArray[divisorMaxLable + 1] = temp;
divisorMaxLable+=1;
if ((temp==0) && (CtrL[8]==0))
{
divisorMaxLable--;
}
temp=0;
MM = CtrL[5] - divisorMaxLable;
for (i = 0; i <=divisorMaxLable; i++)////// 减法，被除数-商*除数
{
Wdiv[i+ MM] -= (TempArray[i]+ temp);
temp = 0;
if (Wdiv[i + MM] >=BASE)
{
Wdiv[i + MM] += BASE;
temp = 1;
}
}
CtrL[4] = 0;
if (temp == 1) /// temp==1表示余数是负的。说明试商比真实商大了一。
{
temp = 0;
for (i = 0; i <=divisorMaxLable; i++)////
{
Wdiv[i + MM] += divisor[i] + temp;// 加法,余数为负数时做一次加法
temp = 0;
if (Wdiv[i +MM] >= BASE)
{
Wdiv[i + MM] -= BASE;
temp = 1;
}/////
}
if (CtrL[6] == 1)///当temp1==1和CtrL[6]==1同时成立时。说明真实的商应该是零。
{
CtrL[4] = 1; //强制让被除数增加一项。
}
CtrL[6] -= 1;//余数为负时，试商减去一
}
return (CtrL[6]);
}
int _Output(UINT32 *quotient,UINT32 *remainder,int *CtrL)/////输出商和余数
{
//CtrL[2]=quotientLEN 传送商（数组）的长度
//CtrL[3]=remainderLEN 传送余数（数组）的长度
int quotientLEN = CtrL[2];
int remainderLEN =CtrL[3];
int i;
printf("被除数\n");///输出被除数
printf("%s",a);
printf("\n");
printf("\n");
printf("除数\n");///输出除数
printf("%s",b);
printf("\n");
printf("\n");
printf("\n");
switch (BASE_EXP)///输出商和余数
{
case 6:
printf("所得商\n");
printf("%d", quotient[quotientLEN - 1]);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%06d", quotient[i]);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder[remainderLEN - 1]);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%06d", remainder[i]);
}
break;
case 5:
printf("所得商\n");
printf("%d", quotient[quotientLEN - 1]);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%05d", quotient[i]);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder[remainderLEN - 1]);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%05d", remainder[i]);
}
break;
case 4:
printf("所得商\n");
printf("%d", quotient[quotientLEN - 1]);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%04d", quotient[i]);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder[remainderLEN - 1]);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%04d", remainder[i]);
}
break;
case 3:
printf("所得商\n");
printf("%d", quotient[quotientLEN - 1]);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%03d", quotient[i]);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder[remainderLEN - 1]);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%03d", remainder[i]);
}
break;
case 2:
printf("所得商\n");
printf("%d", quotient[quotientLEN - 1]);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%02d", quotient[i]);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder[remainderLEN - 1]);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%02d", remainder[i]);
}
break;
case 1:
printf("所得商\n");
printf("%d", quotient[quotientLEN - 1]);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%01d", quotient[i]);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder[remainderLEN - 1]);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%01d", remainder[i]);
}
break;
}
printf("\n");
return 0;
}
int _Input(UINT32 *dividend,UINT32 *divisor,int *CtrL)
{
//CtrL[0]=dividendLEN 传送被除数（数组）的长度
//CtrL[1]=divisorLEN 传送除数（数组）的长度
_RandomNumbers(a,DIVID);////产生DIVID个数字的被除数
_RandomNumbers(b,DIVIS);////产生DIVIS个数字的除数
CtrL[0] = _StringToDigit(dividend, a);///将产生的数字字符存入数组中
CtrL[1] = _StringToDigit(divisor, b);
return 0;
}
void _RandomNumbers(char *a, int lenA)////产生多位数字的十进制随机数
{
int i;
UINT32 seed;
seed = (UINT32)time(0);
srand(rand() + seed);
do
{
a[0] = rand() % 10;////do循环确保随机数的第一位数字非零。
a[0] += 48;
} while (a[0] == 48);
for (i = 1; i < lenA; i++)
{
a[i] = 48 + rand() % 10;
}
a[i] = '\0';
}////*////
int _StringToDigit(UINT32 *result, char *str)////辅助函数。将字符数组转换为数字数组，按10^k进制存入数组中
{
int step=0;
int strInteger;
int strRemainder;
int i,j;
strInteger = strlen(str) / BASE_EXP;////将字符数组str按指数长BASE_EXP分组
strRemainder = strlen(str) % BASE_EXP;
if (strRemainder == 0)
{
for (j=strInteger-1; j>=0; j--, step += BASE_EXP)
{
for (i=step; i <= step+BASE_EXP- 2; i++)
{
result[j] += str[i] - 48;
result[j] *= 10;
}
result[j] += str[i] - 48;
}
}
else
{
for (j=0; j<=strRemainder-2; j++)
{
result[strInteger] += str[j] - 48;
result[strInteger] *= 10;
}
result[strInteger] += str[j] - 48;
for (j=strInteger-1; j>=0; j--, strRemainder += BASE_EXP)
{
for (i = strRemainder; i <= strRemainder+BASE_EXP-2; i++)
{
result[j] += str[i] - 48;
result[j] *= 10;
}
result[j] += str[i] - 48;
}
}
if (strRemainder == 0)
{
strInteger--;
}
return (strInteger + 1);
}
int _resultTest(UINT32 *dividend,UINT32 *divisor,UINT32 *quotient,UINT32 *remainder,int *CtrL)
{
//CtrL[0]=dividendLEN 传送被除数（数组）的长度
//CtrL[1]=divisorLEN 传送除数（数组）的长度
//CtrL[2]=quotientLEN 传送商（数组）的长度
//CtrL[3]=remainderLEN 传送余数（数组）的长度
int i, j;
UINT64 MIDDLE;
UINT32 temp,TEMP;
UINT32 testOne[DIVID/BASE_EXP+3]={0};
UINT32 testTwo[DIVID/BASE_EXP+3]={0};
for (i = 0; i < CtrL[1]; i++)
{
temp = 0;
TEMP = divisor[i];
for (j = 0; j < CtrL[2]; j++)
{
MIDDLE = UInt32x32To64(TEMP , quotient[j]) + temp + testOne[i + j];
temp = (UINT32)(MIDDLE / BASE);
testOne[i + j] = (UINT32)(MIDDLE - UInt32x32To64(BASE , temp));
}
testOne[i + j] = temp;
}
for (i = 0; i < CtrL[0]; i++)
{
testTwo[i]= dividend[i]-testOne[i]-temp;
temp=0;
if(testTwo[i]>=BASE)
{
testTwo[i]+=BASE;
temp=1;
}
}
printf("\n");
j=CtrL[3]-1;
while(testTwo[j]==remainder[j])
{
j--;
if(j<0)
{
printf("结果正确");
}
}
if(j>0)
{
printf("结果错误");
}
printf("\n");
return 0;
}

复制代码

nyy · 发表于 2024-1-5 12:41:46

只是呼吸发表于 2024-1-5 12:35

写个屁呀，现在网上有现成的大整数开源算法（我下载后，根本看不懂），比hugecalc还牛逼，只不过你不知道，
我是亲自体验过后才知道

nyy · 发表于 2024-1-5 12:48:15

https://github.com/ILW8/gwnum

好像就这个开源算法库，吊打hugecalc，所以真的没必要再浪费时间了

TobyFlenderson · 发表于 2024-4-7 10:19:12

无所谓哪个牛逼，最主要的还是学习算法思想吧，理性愉悦嘛。

只是呼吸 · 发表于 2024-5-2 10:07:09

今天发现，除法的结果是正确的，但是检测函数（int _resultTest()）考虑不周到，把正确的结果判错了。

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

[原创] 最优除法步骤试验（附源代码）

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

点评

[原创] 最优除法步骤试验（附 源代码）

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

点评

[原创] 最优除法步骤试验（附源代码）