最优除法步骤试验（附 源代码）
在写大整数的除法过程中，包括本人在内的很多人，因为没有掌握除法的内在联系，走了弯路。
本人用的除法采用的是\(10^8\)进制，最近在扩展到\(10^9\)进制的过程中，就遇到了困难。心想：难道一个进制就要单独写一个除法程序吗？
重新思考后，发现大整数的加法、减法、乘法（硬乘）都有一个共同的特征规律：
1） 输入数据能采用任意\(10^k\)进制，运算结果不受影响（因为计算机字长限制以及编译器不支持的进制除外）。
2） 运算过程中不需要改变输入数据的结构和大小
结合加法、减法、乘法（硬乘）的共同特征规律，我们有理由认为，除法的运算规律也应当如此。
当我们按照上面两个特征规律，结合“笔算除法的最优估商”，写出笔算除法程序时，我们不但得到了商，还同时得到了余数，这个余数是笔算除法的必然结果。
各位爱好者可以查看一下自己写的除法程序，如果余数不是自然得到，而是要添加一些步骤才得到，那么一定是运算过程中“改变了输入数据的结构和大小”。
下面是测试源代码。
说明：源代码做在一个文件中，在debug 模式下编译通过。
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <wtypes.h>
/* 变量长度 */
typedef unsigned int UINT32; /*定义三十二位无符号变量 */
typedef unsigned __int64 UINT64; /*定义六十四位无符号变量 */
/* 一些宏定义 */
#defineBASE1000000 /*大数的基数（10^k进制，可修改）*/
#defineBASE_EXP 6 /*基数的指数 k，与基数同时修改 */
#defineDIVID 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={0}; /*被除数a */
static char b={0}; /*除数b */
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
UINT32dividend={0}; //dividend 被除数
UINT32divisor={0}; //divisor 除数
UINT32quotient={0}; //quotient 商
UINT32remainder={0}; //remainder 余数
int CtrL={0};
//CtrL , 控制数组， 代替结构体传送必须的各个参数
//CtrL=dividendLEN 传送被除数（数组）的长度
//CtrL=divisorLEN 传送除数（数组）的长度
//CtrL=quotientLEN 传送商（数组）的长度
//CtrL=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=dividendLEN 传送被除数（数组）的长度
//CtrL=divisorLEN 传送除数（数组）的长度
//CtrL=quotientLEN 传送商（数组）的长度
//CtrL=remainderLEN 传送余数（数组）的长度
int dividendLEN=CtrL;
int divisorLEN=CtrL;
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=dividend;////// remainder[]是被除数的拷贝，既是工作数组，又得到余数
}
remainderLEN=dividendLEN;
DivHelp(remainder,divisor,quotient,CtrL);//除法
i = DIVIS/BASE_EXP+6;
while ((remainder == 0) && (i >= 0)) /// 计算余数长度
{
i--;
}
CtrL=i+1;
i = dividendLEN-divisorLEN;
while ((quotient == 0) && (i >= 0)) /// 计算商 的长度
{
i--;
}
CtrL=i+1;
return 0;
}
int DivHelp(UINT32*Wdiv, UINT32*divisor, UINT32 *qut, int *CtrL)
{
// Wdiv[]; 被除数的工作数组，同时也是余数数组
// qut[]; 商
//CtrL 传送被除数（数组）的长度
//CtrL 传送除数（数组）的长度
//CtrL 试商由一确定为零时的判断依据
//CtrL 随时刷新的被除数最高位下标(用于除法对位),
//CtrL 传送试商的值
//CtrL 对位计算
// UINT32 TempArray = { 0 };///存储试商与除数相乘所得的结果
UINT64D = 0;
UINT64C = 0;
int divisorMaxLable=CtrL-1; // 除数数组的最大下标
int changeLable=CtrL-1; // 随时刷新的被除数起始下标，初值 CtrL-1
int i;
CtrL = 0;
CtrL=CtrL-1; //随时刷新的被除数起始下标，初值 CtrL-1 做首次计算
CtrL = 0;
i = changeLable - divisorMaxLable; //除法总的循环次数的初始值（从ctrl-ctrl 开始计数）
D = UInt32x32To64(divisor, BASE) +(UINT64)divisor;
while (i >= 0)//-----//除法开始
{
C = UInt32x32To64(Wdiv, BASE) + (UINT64)Wdiv;////-----C=Wdiv*10^8+Wdiv.
if ((C < D) || (CtrL == 1))
{
i--;
if(i<0)
{
continue;
}
C *= BASE;
C += (UINT64)Wdiv;//C=Wdiv*10^2k+Wdiv*10^k+Wdiv
//three_div_two(Wdiv, divisor,CtrL);
CtrL = 1;
}
CtrL = (int)(C / D); /// 求试商
MulSubAdd(Wdiv,divisor,CtrL); /// 被除数-商*除数
if(CtrL==1)continue;
qut = CtrL; ////已定商，赋值给数组
while ((Wdiv == 0) && (changeLable >= 0)) /// 刷新被除数最高位下标changeLable,用于下一次计算
{
changeLable--;
}
i = changeLable - divisorMaxLable;
CtrL=changeLable;
CtrL = 0;
}
}///*/////
int MulSubAdd(UINT32 *Wdiv,UINT32 *divisor,int *CtrL)
{
//CtrL 传送除数（数组）的长度
//CtrL 随时刷新的被除数最高位下标(用于除法对位),
//CtrL 传送试商的值
//CtrL 对位计算
UINT32 TempArray = { 0 };///临时存储试商与除数相乘所得的结果
int divisorMaxLable=CtrL-1; ///除数数组的最大下标
int temp,MM;
int i;
UINT64 C=0,D=0;
temp = 0;
TempArray = 0;
TempArray = 0;
for (i= 0; i <= divisorMaxLable; i++)
{
C = UInt32x32To64(divisor, CtrL) + temp;/// 乘法。 CtrL是函数传入的试商。C=商*除数;
temp = (int)(C / BASE);
TempArray = (int)(C - UInt32x32To64(temp, BASE));
}
TempArray = temp;
divisorMaxLable+=1;
if ((temp==0) && (CtrL==0))
{
divisorMaxLable--;
}
temp=0;
MM = CtrL - divisorMaxLable;
for (i = 0; i <=divisorMaxLable; i++)////// 减法，被除数-商*除数
{
Wdiv -= (TempArray+ temp);
temp = 0;
if (Wdiv >=BASE)
{
Wdiv += BASE;
temp = 1;
}
}
CtrL = 0;
if (temp == 1) /// temp==1表示余数是负的。说明试商比真实商大了一。
{
temp = 0;
for (i = 0; i <=divisorMaxLable; i++)////
{
Wdiv += divisor + temp;// 加法,余数为负数时做一次加法
temp = 0;
if (Wdiv >= BASE)
{
Wdiv -= BASE;
temp = 1;
}/////
}
if (CtrL == 1)///当temp1==1和CtrL==1同时成立时。说明真实的商应该是零。
{
CtrL = 1; //强制让被除数增加一项。
}
CtrL -= 1;//余数为负时，试商减去一
}
return (CtrL);
}
int _Output(UINT32 *quotient,UINT32 *remainder,int *CtrL)/////输出商和余数
{
//CtrL=quotientLEN 传送商（数组）的长度
//CtrL=remainderLEN 传送余数（数组）的长度
int quotientLEN = CtrL;
int remainderLEN =CtrL;
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);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%06d", quotient);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%06d", remainder);
}
break;
case 5:
printf("所得商\n");
printf("%d", quotient);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%05d", quotient);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%05d", remainder);
}
break;
case 4:
printf("所得商\n");
printf("%d", quotient);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%04d", quotient);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%04d", remainder);
}
break;
case 3:
printf("所得商\n");
printf("%d", quotient);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%03d", quotient);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%03d", remainder);
}
break;
case 2:
printf("所得商\n");
printf("%d", quotient);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%02d", quotient);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%02d", remainder);
}
break;
case 1:
printf("所得商\n");
printf("%d", quotient);
for (i = quotientLEN - 2; i >= 0; i--)
{
printf("%01d", quotient);
}
printf("\n");
printf("\n");
printf("所得余数\n");
printf("%d", remainder);
for (i = remainderLEN - 2; i >= 0; i--)
{
printf("%01d", remainder);
}
break;
}
printf("\n");
return 0;
}
int _Input(UINT32 *dividend,UINT32 *divisor,int *CtrL)
{
//CtrL=dividendLEN 传送被除数（数组）的长度
//CtrL=divisorLEN 传送除数（数组）的长度
_RandomNumbers(a,DIVID);////产生DIVID个数字的被除数
_RandomNumbers(b,DIVIS);////产生DIVIS个数字的除数
CtrL = _StringToDigit(dividend, a);///将产生的数字字符存入数组中
CtrL = _StringToDigit(divisor, b);
return 0;
}
void _RandomNumbers(char*a, int lenA)////产生多位数字的十进制随机数
{
int i;
UINT32 seed;
seed = (UINT32)time(0);
srand(rand() + seed);
do
{
a = rand() % 10;////do循环确保随机数的第一位数字非零。
a += 48;
} while (a == 48);
for (i = 1; i < lenA; i++)
{
a = 48 + rand() % 10;
}
a = '\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 += str - 48;
result *= 10;
}
result += str - 48;
}
}
else
{
for (j=0; j<=strRemainder-2; j++)
{
result += str - 48;
result *= 10;
}
result += str - 48;
for (j=strInteger-1; j>=0; j--, strRemainder += BASE_EXP)
{
for (i = strRemainder; i <= strRemainder+BASE_EXP-2; i++)
{
result += str - 48;
result *= 10;
}
result += str - 48;
}
}
if (strRemainder == 0)
{
strInteger--;
}
return (strInteger + 1);
}
int _resultTest(UINT32 *dividend,UINT32 *divisor,UINT32 *quotient,UINT32 *remainder,int *CtrL)
{
//CtrL=dividendLEN 传送被除数（数组）的长度
//CtrL=divisorLEN 传送除数（数组）的长度
//CtrL=quotientLEN 传送商（数组）的长度
//CtrL=remainderLEN 传送余数（数组）的长度
int i, j;
UINT64MIDDLE;
UINT32 temp,TEMP;
UINT32 testOne={0};
UINT32 testTwo={0};
for (i = 0; i < CtrL; i++)
{
temp = 0;
TEMP = divisor;
for (j = 0; j < CtrL; j++)
{
MIDDLE = UInt32x32To64(TEMP , quotient) + temp + testOne;
temp = (UINT32)(MIDDLE / BASE);
testOne = (UINT32)(MIDDLE - UInt32x32To64(BASE , temp));
}
testOne = temp;
}
for (i = 0; i < CtrL; i++)
{
testTwo= dividend-testOne-temp;
temp=0;
if(testTwo>=BASE)
{
testTwo+=BASE;
temp=1;
}
}
printf("\n");
j=CtrL-1;
while(testTwo==remainder)
{
j--;
if(j<0)
{
printf("结果正确");
}
}
if(j>0)
{
printf("结果错误");
}
printf("\n");
return 0;
}
只是呼吸 发表于 2024-1-5 12:35
写个屁呀，现在网上有现成的大整数开源算法（我下载后，根本看不懂），比hugecalc还牛逼，只不过你不知道，
我是亲自体验过后才知道 https://github.com/ILW8/gwnum
好像就这个开源算法库，吊打hugecalc，所以真的没必要再浪费时间了 无所谓哪个牛逼，最主要的还是学习算法思想吧，理性愉悦嘛。 今天发现，除法的结果是正确的，但是检测函数（int _resultTest()）考虑不周到，把正确的结果判错了。
页:
[1]