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

公子相 · 发表于 2024-1-6 21:36:40

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

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

aduxoeroba · 发表于 2024-1-6 21:37:26

#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;}

复制代码

uzmedafacof · 发表于 2024-1-6 21:37:39

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

icakeekohude · 发表于 2024-1-6 21:38:06

https://github.com/ILW8/gwnum

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

		自动登录	找回密码
密码			立即注册

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

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