C++高精度算法的简单实现

一、基本原理1、存储方式采用数字记录高精度数字数组的第一个元素存储数据长度比如记录数字为1024示例如下2、计算方式采用模拟立竖式计算比如加法的计算流程如下图所示10249000这里只给出加法的计算说明其他的以此类推减法与加法基本一致。乘法和除法略有不同通过示例图表示也复杂还不如通过代码去理解本质的方法就是模拟笔算的立竖式计算。二、辅助方法1、字符串转高精度长度记录在数组第一个元素中123456789101112/// summary/// 通过字符串初始化/// /summary/// param namea[in]高精度数组/param/// param namevalue[in]字符串首地址/paramstaticvoidloadStr(int* a,constchar* value){//记录长度a[0] strlen(value);for(inti 1; i a[0]; i)a[i] value[a[0] - i] -0;}2、整型转高精度12345678910111213141516171819/// summary/// 通过无符号整型初始化/// /summary/// param namea[in]高精度数组/param/// param namevalue[in]整型值/paramstaticvoidloadInt(int* a, uint64_t value){for(size_ti 1; i 8096; i){a[i] value % 10;value / 10;if(!value){//记录长度a[0] i;return;}}}3、比较123456789101112131415/// summary/// 比较两个高精度数的大小/// /summary/// param namea[in]第一个数/param/// param nameb[in]第二个数/param/// returns1是ab,0是ab,-1是ab/returnsstaticintcompare(int* a,int* b){if(a[0] b[0])return1;if(a[0] b[0])return-1;for(inti a[0]; i 0; i--)if(a[i] b[i])return1;elseif(a[i] b[i])return-1;return0;}4、打印123456789/// summary/// 打印输出结果/// /summarystaticvoidprint(int* a) {if(!a[0])printf(0);for(inti a[0]; i 0; i--)printf(%d, a[i]);}三、算法实现原理就不做具体介绍了四种计算的核心都是模拟立竖式计算。1、加法为了保证代码相对简单当b长度较小时可能会做一些多余的计算不影响结果。123456789101112131415161718/// summary/// 加法(累加)///结果会保存在a中/// /summary/// param namea[in]被加数/param/// param nameb[in]加数/paramstaticvoidacc(int* a,int* b){intlen a[0] b[0] ? a[0] : b[0];memset(a a[0] 1, 0, (len - a[0] 1) *sizeof(int));memset(b b[0] 1, 0, (len - b[0] 1) *sizeof(int));for(inti 1; i len; i) {inttemp a[i] b[i];a[i] temp % 10;a[i 1] temp / 10;}if(a[len 1])a[0];}2、减法12345678910111213141516171819202122232425262728/// summary/// 减法(累减)///结果会保存在a中/// /summary/// param namea[in]被减数被减数必须大于等于减数/param/// param nameb[in]减数/paramstaticvoidsubc(int* a,int* b) {memset(b b[0] 1, 0, (a[0] - b[0]) *sizeof(int));for(inti 1; i a[0]; i){inttemp a[i] - b[i];a[i] temp;if(temp 0){//借位a[i 1] - 1;a[i] 10;}}//记录长度for(inti a[0]; i 0; i--)if(a[i]){a[0] i;return;}a[0] 0;}3、乘法123456789101112131415161718192021222324252627282930313233/// summary/// 乘法/// /summary/// param namea[in]被乘数/param/// param nameb[in]乘数/param/// param namec[out]结果数组长度必须大于等于aLenbLen1/paramstaticvoidmul(int* a,int* b,intc[]) {c[a[0] b[0]] 0;memset(c, 0,sizeof(int) * (a[0] b[0] 1));for(inti 1; i a[0]; i){intj;intd 0;//被乘数的一位去乘以乘数的每一位for(j 1; j b[0]; j){inttemp a[i] * b[j] c[j i - 1] d;c[j i - 1] temp % 10;d temp / 10;}if(d){c[j i - 1] d;}}//记录长度for(inti a[0] b[0]; i 0; i--)if(c[i]){c[0] i;return;}}4、除法采用了升阶减法实现123456789101112131415161718192021222324252627282930313233343536/// summary/// 除法/// 依赖减法subc/// /summary/// param namea[in]被除数,被除数必须大于除数/param/// param nameb[in]除数/param/// param namec[out]商数组长度大于等于aLen-bLen1/param/// param namemod[out]余数数组长度大于等于aLen/param/// param nametemp[in]临时缓冲区由外部提供以提高性能数组长度大于等于aLen-bLen1/paramstaticvoiddivi(int* a,int* b,int* c,int* mod,int* temp) {//相差的阶数intdigit a[0] - b[0] 1;memcpy(mod, a, (a[0] 1) *sizeof(int));memset(c, 0,sizeof(int) * (digit 1));memset(temp, 0,sizeof(int) * digit);while(digit){//升阶memcpy(temp digit, b 1,sizeof(int) * b[0]);temp[0] b[0] digit - 1;//减法while(compare(mod, temp) ! -1){subc(mod, temp);c[digit];}digit--;}//记录长度for(inti a[0] - b[0] 1; i 0; i--)if(c[i]){c[0] i;return;}}四、使用示例1、加法计算累加1234567891011121314intmain() {int64_t n;intnum[1024];intnum2[1024];std::cin n;loadInt(num, 0);for(int64_t i 1; i n; i){loadInt(num2, i);acc(num, num2);}print(num);return0;}结果2、减法两个任意n位数的减法数字1大于数字2。1234567891011intmain(){inta1[8096], a2[8096];std::string s1, s2;std::cin s1 s2;loadStr(a1, s1.c_str());loadStr(a2, s2.c_str());subc(a1, a2);print(a1);return0;}结果#数字1752425289999999999999652142141414141414146666676667677682324000001302461646520#数字2587891851201874512000000000154515100202121555555555555555555555545477910232111#计算结果1645334387981254879996521419868990412120251111211121221267684444558245514144093、乘法计算阶乘1234567891011121314151617181920intmain() {int64_t n;intnum[8192];intnum2[8192];intnum3[8192];int* p1 num;int* p2 num3;std::cin n;loadInt(num, 1);for(int64_t i 1; i n; i){loadInt(num2, i);mul(p1, num2, p2);int* temp p1;p1 p2;p2 temp;}print(p1);return0;}