跳转链接高精度计算入门与immense数据模型精讲一高精度计算入门与immense数据模型精讲二高精度计算入门与immense数据模型精讲三高精度计算入门与immense数据模型精讲五高精度计算入门与immense数据模型精讲六高精度计算入门与immense数据模型精讲七高精度计算入门与immense数据模型精讲八高精度计算入门与immense数据模型精讲九immense大实数数据库前言从比较到运算竖式思想的第一次完整落地前面三篇我们搭建了存储模型、搞定了归一化规则、讲透了比较逻辑完成了高精度库的全部基础准备。从本篇开始我们正式进入运算模块。加减是所有竖式运算的起点逻辑最直观也最能体现「模拟人手计算」的核心思想。很多人接触高精度都是从「大数加法」的算法题开始的但真正写好支持小数的实数加减并不简单小数点怎么对齐进位如何跨整数与小数传递借位不够怎么办正负数混合运算如何统一逻辑这些问题处理不好代码就会充满分支bug丛生。本篇依然严格遵循「通用原理先行代码实现对照」的教学节奏先把十进制高精度加减的通用方法论讲透从无符号整数到实数再到带符号运算的统一处理再对照immense的源码逐行拆解Add、Less、Centre_AL三个核心函数看它们如何把通用思想落地。一、通用原理高精度加减的核心方法论1.1 本质把小学竖式搬进代码高精度加法和减法的底层逻辑和我们小学学的手算完全一致。人手算加法的标准步骤右对齐个位对个位、十位对十位保证相同权重的数位对齐从低位算起从最右侧的个位开始逐位相加满十进一每一位相加超过10就向高位进1最高位进位所有位算完还有进位结果多一位减法的步骤对称右对齐从低位算起不够减就向高位借1当10必须保证被减数大于等于减数否则交换位置结果加负号计算机做高精度加减就是把这个过程用数组/字符串复刻出来。唯一的变量是存储顺序——存储方式不同对齐和遍历的方向也不同。1.2 无符号整数加法通用算法前提约定两个非负整数采用倒序存储低位在下标0。这是高精度整数最主流的存储方式。标准算法步骤以较长的数为基准较短的数高位等效补零循环超出长度按0处理初始化进位变量carry 0从下标0开始正序遍历每一位当前位和 甲位数值 乙位数值 低位进位当前位结果 和 % 10新的进位 和 / 10遍历结束后如果carry 0在结果末尾追加一位进位结果天然为倒序无需额外反转时间复杂度O(n)n 为较长数的位数。加法是线性时间运算没有更快的通用算法。教学要点为什么倒序存储是加法的最佳选择因为最低位在下标0两个数的最低位天然对齐循环从0开始正序走即可进位产生的新位直接追加到字符串末尾均摊O(1)。如果是正序存储不仅要从末尾往前遍历进位还要插入到字符串头部时间复杂度变成O(n)麻烦很多。1.3 无符号整数减法通用算法减法比加法多一条铁律必须保证被减数 ≥ 减数否则会出现无限借位的逻辑错误。标准算法步骤前置判断若被减数 减数交换两者标记结果为负初始化借位变量borrow 0从下标0开始正序遍历每一位被减数当前位先减去低位来的借位如果被减数位 减数位被减数位 10新借位 1否则新借位 0结果位 被减数位 - 减数位遍历结束后清理结果的前导零倒序存储即清理末尾的零根据标记决定是否给结果加负号重点连续借位的处理比如计算1000 - 1需要从千位一路借位到个位中间连续三位都是0。算法中的borrow变量会逐位传递只要循环完整走完就能自动处理连续借位不需要额外写特殊分支。这是很多初学者容易卡壳的地方。1.4 实数加减小数点对齐是核心从整数扩展到实数唯一新增的复杂度就是小数点对齐。只有小数点对齐了相同权重的数位才能正确相加减。通用对齐方法两个实数相加减先统一小数位数小数位数少的尾部补零让两者小数长度相同对齐之后小数部分和整数部分就可以分别按整数加减处理加法的进位会从小数部分传递到整数部分减法的借位会从整数部分传递到小数部分举个直观例子12.34 5.678统一小数位数12.340 5.678小数部分相加340 678 1018保留018进位1传给整数整数部分相加12 5 1 18合并结果18.018教学要点实数加减的本质就是「对齐小数点 → 当成大整数加减 → 还原小数点」。所有实数高精度加减最终都会退化成整数加减。小数点对齐是实数库独有的额外工作量。1.5 带符号运算符号中心化统一处理前面讲的都是无符号数的加减。但实际使用中数有正有负加法和减法还可以互相转化。如果每种符号组合都写一套逻辑代码会极其冗余也容易出错。工程上的通用最佳实践叫符号中心化所有带符号的加法和减法都先取绝对值转化成两个无符号数的运算根据两个数的符号决定最终做加法还是减法运算结束后再回填正确的符号。具体来说对于任意a op bop 可以是 或 -先统一成a (±b)的形式减法等价于加相反数取两者绝对值 |a|、|b|同号结果 无符号加(|a|, |b|)符号与 a 相同异号用大的绝对值减小的绝对值符号与绝对值大的一方相同这样一来无论正加正、正减负、负加正、负减负全部复用同一套无符号 Add 和 Less 函数。外层只处理符号调度内层只专心算数值。这就是「符号与数值分离」设计的最大价值。1.6 必须覆盖的边界案例写好加减运算一定要用以下边界用例验证零加任何数 任何数相等两数相减 0全进位999 1 1000位数增加全借位1000 - 1 999位数减少小数跨整数进位0.9 0.2 1.1跨小数点借位1.0 - 0.1 0.9异号相加结果为零123 (-123) 0这些案例覆盖了进位、借位、符号、零值所有关键路径是检验加减实现正确性的试金石。二、immense 实现对照加减三函数逐行精讲immense的加减体系严格遵循上述通用原理采用经典的三层架构底层运算层Add无符号实数加、Less无符号实数减中层调度层Centre_AL符号中心化调度上层接口层运算符重载、-、、-、自增自减我们从底层往上层逐段拆解。2.1 Add 函数无符号实数加法完整源码immense Add(immense local,immense other){ std::string xlocal.DCMp,yother.DCMp; while(x.size()y.size()) x.push_back(0); while(y.size()x.size()) y.push_back(0); int carry0,p,q; for(int i(int)y.size()-1;i0;i--){ px[i]-0; qy[i]-0; x[i](pqcarry)%100; carry(pqcarry)/10; } local.DCMpx; xlocal.LTGp,yother.LTGp; if(x.size()y.size()) std::swap(x,y); int i; for(i0;iy.size();i){ px[i]-0; qy[i]-0; x[i](pqcarry)%100; carry(pqcarry)/10; } while(ix.size()carry){ int tx[i]-0; x[i](tcarry)%100; carry(tcarry)/10; i; } if(carry)xx1; local.LTGpx; local.rationalize(); return local; }对照通用原理拆解为三个阶段第一阶段小数部分对齐与相加std::string xlocal.DCMp,yother.DCMp; while(x.size()y.size()) x.push_back(0); while(y.size()x.size()) y.push_back(0);先对小数部分补零对齐短的尾部补零让两者长度一致。完全对应「小数点对齐」的通用步骤。for(int i(int)y.size()-1;i0;i--){ px[i]-0; qy[i]-0; x[i](pqcarry)%100; carry(pqcarry)/10; }小数是正序存储最低位在字符串末尾所以从后往前遍历。逐位相加记录进位。这里产生的carry会从小数最低位一直传递到小数最高位十分位然后继续传递给整数部分实现跨小数点的进位衔接。第二阶段整数部分相加xlocal.LTGp,yother.LTGp; if(x.size()y.size()) std::swap(x,y);整数部分是倒序存储低位在下标0。先把长的放前面保证循环基准统一。for(i0;iy.size();i){ px[i]-0; qy[i]-0; x[i](pqcarry)%100; carry(pqcarry)/10; }从下标0开始正序遍历对应从低位到高位。这里的carry就是小数部分传过来的进位天然衔接。完全匹配通用整数加法算法。while(ix.size()carry){ int tx[i]-0; x[i](tcarry)%100; carry(tcarry)/10; i; } if(carry)xx1;短的数遍历完后如果还有进位就继续处理长数的剩余位。最后如果仍有进位在字符串末尾追加一位。对应通用算法的「剩余位处理 最终进位」两步。第三阶段归一化收尾local.rationalize(); return local;运算完成后统一调用归一化同步长度变量清理可能产生的无效零。这是immense所有运算的标准收尾动作。2.2 Less 函数无符号实数减法完整源码immense Less(immense local,immense other){ if(localother)return immense(long(0)); if(localother) return -Less(other,local); int carry0,x0,y0; char ch; while((int)local.DCMp.size()other.DCMn)local.DCMp.push_back(0); while((int)other.DCMp.size()local.DCMp.size()) other.DCMp.push_back(0); for(int i(int)other.DCMn-1;i0;i--){ xlocal.DCMp[i]-0; yother.DCMp[i]-0; local.DCMp[i](x-carry-y10)%100; carry(x-carry-y)0; } int i0; for(;iother.LTGn;i){ xlocal.LTGp[i]-0; yother.LTGp[i]-0; local.LTGp[i](x-carry-y10)%100; carry(x-carry-y)0; } while(carry){ if(i(int)local.LTGp.size()) local.LTGp.push_back(0); chstatic_castunsigned char(local.LTGp[i])-1,carry0; if(ch0) ch10; local.LTGp[i] static_castchar(ch); i; } local.rationalize(); return local; }对照通用减法原理分步拆解第一步前置校验与交换保证if(localother)return immense(long(0)); if(localother) return -Less(other,local);这是减法的标准前置处理两数相等直接返回0若被减数小于减数交换位置递归调用结果取负保证进入后续逻辑时被减数一定 ≥ 减数不会出现负结果完全对应通用减法的前提保证。第二步小数部分对齐与相减while((int)local.DCMp.size()other.DCMn)local.DCMp.push_back(0); while((int)other.DCMp.size()local.DCMp.size()) other.DCMp.push_back(0);和加法一样先补零对齐小数位数。for(int i(int)other.DCMn-1;i0;i--){ xlocal.DCMp[i]-0; yother.DCMp[i]-0; local.DCMp[i](x-carry-y10)%100; carry(x-carry-y)0; }从小数末尾最低位开始往前减。carry在这里是借位标记1表示需要借位0表示不需要。技巧(x - carry - y 10) % 10这个写法无论够不够减都能算出正确的当前位不用写 if-else 分支简洁且不易出错。第三步整数部分相减int i0; for(;iother.LTGn;i){ xlocal.LTGp[i]-0; yother.LTGp[i]-0; local.LTGp[i](x-carry-y10)%100; carry(x-carry-y)0; }整数倒序存储从下标0低位开始正序遍历。借位从小数部分传过来天然衔接。计算逻辑和小数部分完全一致。第四步连续借位处理while(carry){ if(i(int)local.LTGp.size()) local.LTGp.push_back(0); chstatic_castunsigned char(local.LTGp[i])-1,carry0; if(ch0) ch10; local.LTGp[i] static_castchar(ch); i; }减数遍历完后如果还有借位就继续处理被减数的剩余高位。这就是处理「连续借位」的逻辑比如1000 - 1借位会一路传递下去。因为前置已经保证了被减数更大所以借位最终一定会清零不会无限循环。第五步归一化收尾减法一定会产生前导零倒序存储即末尾的零比如1000 - 1 0999所以必须调用rationalize清理前导零同步长度。2.3 Centre_AL符号中心化调度器Centre_AL是加减运算的中枢对应通用原理的「符号中心化」思想负责把所有带符号运算调度到无符号的Add和Less上。完整源码immense Centre_AL(immense x,bool AmS,immense y){ if(!AmS)return Centre_AL(x,true,-y); immense result; bool px.symbol,qy.symbol; x.abs(),y.abs(); if(p){ if(q) resultAdd(x,y); else resultLess(x,y); } else{ if(q) resultLess(y,x); else result-(Add(x,y)); } return result; }参数说明x第一个操作数AmStrue表示加法false表示减法y第二个操作数第一步减法转加法if(!AmS)return Centre_AL(x,true,-y);如果是减法就转化成「x 加 -y」递归调用加法版本。这样所有运算最终都统一成加法形式后面只需要处理同号、异号两种情况分支数量减半。第二步符号与数值分离bool px.symbol,qy.symbol; x.abs(),y.abs();保存两个数的符号然后取绝对值后续只计算绝对值。第三步四分支调度if(p){ if(q) resultAdd(x,y); // 正 正 直接加 else resultLess(x,y); // 正 负 正减正 } else{ if(q) resultLess(y,x); // 负 正 正减负 else result-(Add(x,y));// 负 负 相加取负 }四种符号组合对应四种调度正正直接相加结果为正正负大数减小数结果符号随大数负正交换顺序逻辑同上负负绝对值相加结果取负Less函数内部已经处理了「谁大谁小」的问题所以这里直接传参即可无需额外判断大小。2.4 运算符层统一接口封装上层的所有运算符全部调用Centre_AL代码极其简洁inline immense immense::operator(const immense other)const{ immense tother; return Centre_AL(*this,true,t); } inline immense immense::operator-(const immense other)const{ immense tother; return Centre_AL(*this,false,t); }复合赋值、自增自减也是同理复用inline void immense::operator(const immense other){ immense tother; *thisCentre_AL(*this,true,t); } inline immense immense::operator(){ *thisCentre_AL(*this,true,immense(1)); return *this; }自增自减本质就是加/减1完全复用同一套逻辑。这种分层设计的优势非常明显底层Add/Less只关心无符号运算逻辑纯粹中层Centre_AL只关心符号调度不碰具体运算上层运算符只做接口包装零逻辑冗余出问题排查方便改bug只改对应层三、拓展加减运算的性能与设计权衡3.1 时间复杂度分析加减运算都是线性时间 O(n)n 为总位数。加法一次遍历完成常数因子很小减法同样一次遍历但前置有一次比较判断大小常数因子略大在高精度运算体系里加减是最快的基础运算也是所有高级运算的基石——乘法、除法、开方、级数内部都会大量调用加减。3.2 关键设计权衡点评整数倒序 小数正序的不对称存储优点小数点平移方便进位借位的传递方向与遍历方向天然匹配缺点整数和小数遍历方向相反增加少量心智负担综合来看对于支持小数的实数库是利大于弊的选择值传递而非常量引用Add和Less的参数都是值传递函数内部直接修改副本返回。优点代码书写直观不用创建额外临时变量缺点会触发一次字符串拷贝对于教学级、工具级库来说可读性优先这个取舍非常合理中心化统一调度用Centre_AL把所有加减统一调度是非常经典的工程做法。虽然多了一层函数调用但代码复用率极高符号逻辑只写一次大幅降低了出错概率。3.3 自我验证练习学到这里你可以自己推演几个案例对照代码逻辑走一遍检验是否真正理解immense(0.9) immense(0.2)→ 小数进位到整数结果 1.1immense(1.0) - immense(0.1)→ 跨小数点借位结果 0.9immense(999.99) immense(0.01)→ 全进位结果 1000.0immense(-123) immense(45)→ 异号相减结果 -78如果都能正确推演说明你已经完全掌握了高精度加减的核心逻辑。四、本篇小结与下篇预告4.1 核心知识点回顾通用原理部分加减本质是模拟竖式计算核心是进位和借位的传递处理倒序存储的整数最适合加减低位天然对齐进位追加方便实数加减的关键是小数点对齐统一小数位数后转成整数加减带符号运算的最佳实践是符号中心化取绝对值 → 调度无符号运算 → 回填符号减法必须保证被减数 ≥ 减数否则交换位置结果取负实现对照部分Add函数对齐小数 → 小数带进位相加 → 整数带进位相加 → 最终进位处理 → 归一化Less函数前置保证被减数大 → 对齐小数 → 小数借位相减 → 整数借位相减 → 连续借位处理 → 归一化Centre_AL减法转加法 → 符号分离 → 四分支调度 → 返回带符号结果运算符层全部复用中心化函数分层清晰无逻辑冗余4.2 下篇预告加减是线性运算乘法就不一样了。普通竖式乘法是 O(n²)对于大数来说性能很差。工业级高精度库都会用更快的乘法算法比如Karatsuba 分治乘法可以把时间复杂度降到 O(n^1.585)。下一篇我们就来讲乘法先讲普通竖式乘法的通用原理再讲 Karatsuba 分治乘法的算法思想与复杂度推导最后对照immense的源码看它如何实现普通竖式与 Karatsuba 的自动切换以及如何处理实数乘法的小数点位置。
