高精度计算入门与immense数据模型精讲（二）

跳转链接高精度计算入门与immense数据模型精讲一高精度计算入门与immense数据模型精讲三高精度计算入门与immense数据模型精讲四高精度计算入门与immense数据模型精讲五高精度计算入门与immense数据模型精讲六高精度计算入门与immense数据模型精讲七高精度计算入门与immense数据模型精讲八高精度计算入门与immense数据模型精讲九immense大实数数据库前言为什么规范化是高精度库的第一课上一篇我们搞懂了高精度计算的核心思想——用数组或字符串模拟数位把人脑的竖式运算搬进代码也理清了immense的存储模型整数倒序、小数正序、符号独立。很多人学到这里就急着去写加法、写乘法但真正写过完整高精度库的人都知道运算逻辑只占工作量的一半另一半都在处理“边界和规范”。试想这些场景用户输入000123.45000前导零和尾部零要不要保留除法算出了 2000 位小数但我们只需要 100 位多余的怎么办输入里混进了字母或空格是直接报错还是尽量提取有效数字数值是零的时候符号应该是正还是负允许“负零”存在吗这些问题不统一后面的比较、加减、乘除全都会出bug。比如带着前导零去比大小位数判断就会出错带着尾部零去做循环每一轮都白白浪费性能如果允许负零存在0 -0就会返回假整个逻辑体系都会崩塌。所以所有成熟的高精度库都会确立一套数据不变式Invariant任何时刻对象内部的数据都必须满足这组规则。而负责维护不变式的函数就叫归一化规范化函数。它是高精度库的“守门员”也是所有运算的起点和终点。本篇我们就先从通用原理讲起搞清楚一个规范的高精度数应该满足哪些标准归一化有哪些通用算法分别怎么实现高精度数的输入输出有哪些通用方法和注意事项讲透原理之后再对照immense的源码看它是如何把这些通用思想落地成具体代码的。一、通用原理高精度数的规范化1.1 什么是数据不变式在软件工程里“不变式”指的是一组始终为真的断言。对于高精度数来说不变式就是“数位存储的游戏规则”。举个最简单的例子整数部分除了数值 0 本身不允许出现前导零。这就是一条不变式。如果所有函数都遵守它那么写比较算法的时候就可以放心地用“位数多的数更大”这条结论如果不遵守位数就失去了意义每一步都要额外判断。规范化函数的价值就是把“维护不变式”的工作集中到一个地方。所有修改数位的操作最后只需要调用一次规范化就能保证对象回到合法状态。这极大地降低了整体代码的复杂度。1.2 规范化的五项通用标准对于支持小数的十进制高精度实数库通用的规范化标准有五条几乎所有同类库都会遵守标准说明不遵守的危害字符合法数位串中只能出现0~9运算时出现乱码结果整数无前导零最高位不能是 0纯 0 除外位数虚高比较、对齐全部出错小数无尾部零最低位不能是 0无效循环性能浪费长度一致长度缓存与实际字符串长度相等数组越界、循环边界错误零值唯一零的符号统一为正不允许负零相等判断失效符号逻辑混乱这五条看起来简单但每一条都对应着一类 bug。新手写高精度库十有八九都会在前导零、负零这两个坑里栽跟头。1.3 整数部分的前导零清理通用算法前导零清理是规范化的核心。但要注意存储顺序不同前导零的位置也不同。情况一正序存储的整数如果整数部分高位在前和书写顺序一致那么前导零就在字符串的开头。清理算法是从左往右遍历找到第一个非零字符的位置把从开头到这个位置之前的字符全部删掉如果删空了补一个0伪代码i 0 while i len(s) and s[i] 0: i 1 if i len(s): s 0 else: s s.substr(i)情况二倒序存储的整数如果整数部分低位在前immense采用的方案那么最高位在字符串的末尾前导零也就在字符串末尾。清理算法反过来从右往左遍历找到第一个非零字符的位置把末尾多余的零截掉如果删空了补一个0伪代码i len(s) - 1 while i 0 and s[i] 0: i - 1 s s.substr(0, i 1)教学要点很多初学者记不清前导零在哪头记住一句话就行——前导零永远在最高位那一侧。正序存储最高位在左前导零就在左倒序存储最高位在右前导零就在右。1.4 小数部分的尾部零清理通用算法小数部分的规律更简单无论库怎么设计尾部零永远在小数的最右端也就是精度最低的位置。通用清理算法从右往左遍历小数串遇到 0 就删遇到第一个非零就停止允许删空空就表示没有小数位伪代码i len(s) - 1 while i 0 and s[i] 0: i - 1 s s.substr(0, i 1)小数尾部零清理和整数前导零清理本质上是对称的——都是去掉“最高权重一侧”之外的无效零。1.5 非法字符的两种处理策略如果输入的字符串里混进了非数字字符通常有两种处理策略策略一严格模式Fail-fast只要遇到一个非法字符整个数作废重置为 0 或抛出异常优点数据安全不会静默出错适用场景校验严格的系统、自动化输入策略二宽松模式Best-effort剔除非法字符保留其余有效数字继续使用优点容错性好对用户输入友好适用场景交互式输入、人工录入场景工业级库一般默认严格教学和工具库一般默认宽松。immense采用的是“可切换双模式”默认宽松通过全局开关切换。1.6 零值的唯一性处理这是最容易被忽略的一点。当整数为 0 且小数为空时这个数就是零值。零值的符号必须统一绝大多数库都规定零为正。为什么不能有负零因为数学上0 -0但如果符号位不同operator就会返回假后续所有依赖相等判断的逻辑除法试商、循环终止、去重都会出问题。通用做法规范化函数末尾加一句判断——如果数值为零强制符号为正。二、immense 实现对照rationalize 逐行精讲明白了通用原理再看immense的rationalize()就非常清晰了。它严格按照“先整数、后小数、最后收尾”的顺序完整实现了上述五条标准。2.1 整数部分清理倒序串的前导零处理对应源码bool Ttrue; for(int istatic_castint(LTGp.size())-1;i0;){ if(LTGp[i]9||LTGp[i]0){ if(TreatmentErase){ *thisimmense(); break; } else LTGp.erase(i,1); } else if(TLTGp[i]0LTGp!0)LTGp.erase(i,1); else Tfalse; if(i(int)LTGp.size()) i--; else --i; } if(LTGp)LTGp0;对照原理来读从后往前遍历因为LTGp倒序存储前导零在字符串末尾所以从size()-1往左走标志位Ttrue表示“还没遇到有效数字当前遇到的零都是前导零”遇到第一个非零后置为false后面的零不再删除非法字符分支根据TreatmentErase全局开关选择严格重置或宽松删除索引修正删除字符后字符串变短不能盲目i--要判断当前位置是否仍然有效空串兜底如果删空了补成0常见坑点提醒很多人写前导零清理时会漏掉LTGp!0这个条件导致数值本身就是 0 时被删空。immense这里既在循环里加了判断又在循环外兜底属于双重保险。2.2 小数部分清理截断 尾部零 非法字符对应源码Ttrue; if(DCMp.size()MaxLen) DCMp.resize(MaxLen); for(int istatic_castint(DCMp.size())-1;i0;i--){ if(DCMp[i]9||DCMp[i]0){ if(TreatmentErase){ *thisimmense(); break; } else DCMp.erase(i,1); } else if(TDCMp[i]0)DCMp.erase(i,1); else Tfalse; if(i(int)DCMp.size())i--; else --i; }和整数部分高度对称但多了一步硬截断先截断再清理用MaxLen全局参数把小数长度限制在最大精度以内。这是实数高精度库必备的安全阀——除法、开方、泰勒级数都会产生无限小数如果不截断内存会被无限撑大从后往前清理尾部零小数正序存储尾部零就在字符串末尾逻辑和整数前导零清理完全对称同样的非法字符双策略和整数部分共用同一个开关教学要点为什么先截断再清理而不是先清理再截断因为截断是硬上限不管后面有没有有效数字都要砍掉尾部零清理是在截断范围内再优化。如果先清理再截断可能会把截断位置后面的无效零也清理了白做无用功。2.3 收尾三步同步长度、统一零符号LTGnLTGp.size(); DCMnDCMp.size(); if(LTGp0DCMn0) symboltrue;三步分别对应三条不变式同步整数长度缓存同步小数长度缓存零值强制符号为正这三行代码虽然短但极其重要。尤其是最后一句一行代码解决了“负零”这个经典bug。到这里五项不变式全部得到保证对象回到了完全规范的状态。后续所有运算都可以基于“输入一定是规范的”这个假设来写不用再反复判断边界。三、通用原理高精度数的输入与输出规范化是内部规则而构造与转换是对外的门户。一个高精度数怎么从外部格式整数、浮点数、字符串变成内部的规范格式又怎么转回去里面有很多通用方法论。3.1 为什么字符串才是高精度的“一等公民”先明确一个重要认知在高精度库里只有字符串构造是真正无损的、能体现“任意精度”价值的。整数构造其次浮点数构造本质上只是便利转换。原因很简单long最多 64 位也就十几位十进制本身就在原生类型范围内double只有 53 位尾数对应 15~17 位有效数字从它构造出来的高精度数精度不可能超过它本身只有字符串你写多少位就是多少位一千位、一万位都可以所以学习高精度输入重点要掌握的是字符串解析和字符串输出。3.2 从整数构造除十取余法把原生整数转成高精度数位通用方法叫除十取余法每次对 10 取余得到当前最低位把数字除以 10去掉最低位循环直到数字变成 0这个方法有个非常巧妙的特性先得到的是低位后得到的是高位。所以如果你的整数部分采用倒序存储低位在下标 0那么除十取余得到的顺序刚好和存储顺序一致直接 push_back 就行不需要额外反转。如果是正序存储反而要最后反转一次。这也是倒序存储的优势之一整数构造更自然。3.3 从字符串构造拆分 反转字符串解析是最通用的高精度输入方式通用流程分四步处理符号看首字符是不是负号记录符号后去掉拆分整数小数找小数点切成左右两段整数段反转用户输入是正序倒序存储需要反转一次调用规范化清理前导零、尾部零、非法字符这个流程适用于几乎所有十进制字符串高精度库。immense也是严格按这个顺序实现的。3.4 从浮点数构造乘十取整法把浮点数的小数部分提取出来通用方法叫乘十取整法减去整数部分得到纯小数乘以 10取整数部分就是十分位减去整数部分剩下的继续乘以 10得到百分位循环直到小数变成 0或达到精度上限但这里有一个非常重要的知识点二进制浮点数转十进制小数绝大多数是不精确的。比如 0.1 在二进制里是无限循环小数存在 double 里本身就是近似值。你用乘十取整法提取出来的小数十几位之后就全是噪声了。所以从 double 构造高精度数只能当“方便的近似入口”绝对不能当高精度数据源。想要真正的高精度必须用字符串。3.5 转回字符串无损输出十进制高精度库转字符串非常简单整数部分如果是倒序反转一次拼回去有小数就拼上小数点和小数部分负数前面加负号因为内部就是十进制不需要任何进制转换输出是完全无损的。这也是十进制存储的一大优势——输入输出成本极低调试极其方便。3.6 转回原生类型截断与溢出把高精度数转回 long 或 double本质上都是“有损压缩”有两个共同原则只取有效位超过原生类型容量的高位直接丢弃边界保护要么断言、要么抛出异常至少要让调用者知道溢出了转回整数一般是截断取整只取整数部分相当于 trunc转回浮点数则是用前 15 位左右有效数字做近似超出精度的部分丢掉。四、immense 实现对照构造、赋值与转换4.1 从 long 构造天然倒序的便利void immense::operator(const long T){ long tT; std::string s; bool negfalse; if(t0)negtrue,t-t; if(t0)s0; else while(t0) s.push_back(char((t%10)0)),t/10; this-LTGps; this-DCMp; this-symbol!neg; rationalize(); }对照原理来看标准的除十取余法先处理符号再算绝对值每次t%10得到个位push_back进字符串因为LTGp是倒序存储所以顺序刚好对上不需要反转最后调用rationalize()收尾保证规范这就是倒序存储设计带来的自然契合。4.2 从字符串构造标准四步流程void immense::operator(const std::string T) { std::string rdT,rdL,rdD; symboltrue; if(rd[0]-){ symbolfalse; rd.erase(0,1); } // 找小数点拆分 for(int i0;ird.size();i) if(rd[i].){ rdLrd.substr(0,i); rdDrd.substr(i1); goto assignment; } rdLrd; rdD; assignment:; reverse(rdL.begin(),rdL.end()); LTGprdL,DCMprdD; rationalize(); }完全对应通用四步处理负号查找小数点拆分整数、小数段整数段反转适配倒序存储调用规范化收尾这里用goto跳出循环是 C/C 里的常见写法比设置标志位再判断更直接高效。4.3 从 double 构造近似转换void immense::operator(const double T){ double tT; immense res; if(t0)t-t,res.symbolfalse; reslong(t); t-std::floor(t); while(t1e-16){ t*10; long intPart(long)std::floor(t); res.DCMpchar(intPart0); t-intPart; } res.rationalize(); *thisres; }标准的乘十取整法整数部分直接复用 long 赋值小数部分循环乘 10 取整循环终止条件1e-16对应 double 的精度极限再往后都是噪声再次强调这是有损转换。如果你需要百位以上的高精度务必用字符串初始化。4.4 转回字符串无损还原immense::operator std::string()const{ std::string k; if(!symbol)k-; std::string tmpLTGLTGp; reverse(tmpLTG.begin(),tmpLTG.end()); ktmpLTG; if(DCMn!0)kk.DCMp; return k; }和通用方法完全一致负号 反转后的整数 可选小数部分。十进制存储的优势在这里体现得淋漓尽致——没有任何进制转换开销输出就是原样还原。4.5 转回 long / double有损压缩两个转换函数都严格遵循“取前若干位 边界保护”的原则转 long 最多取 15 位最后断言检查是否溢出转 double 整数部分通过 long 中转小数部分累加 15 位最后断言排除 inf/nan它们的定位都是“和外部代码交互的桥梁”而不是高精度计算的一部分。真正的高精度运算全程都在immense对象内部完成只有输入输出时才和原生类型打交道。五、本篇小结与下篇预告5.1 核心知识点回顾本篇我们以“原理先行、代码对照”的方式完整讲透了规范化和类型转换两大模块。通用原理部分数据不变式是高精度库稳定运行的基石规范化五项标准字符合法、无前置零、无尾部零、长度一致、零值唯一整数前导零清理存储顺序决定清理方向倒序从后往前清小数尾部零清理永远从后往前清输入输出字符串是一等公民double 构造只是近似转换实现对照部分rationalize()完整实现了全部五项规范化标准三种构造路径分别对应除十取余、字符串解析、乘十取整三种通用方法类型转换遵循“无损输出字符串有损转回原生类型”的原则到这里一个immense对象从创建到规范化、再到转出的完整生命周期你就全部掌握了。5.2 下篇预告数据规范了接下来就要开始运算。而所有运算的基础是比较大小。别小看比较——它没有进位借位那么复杂但细节极多符号怎么比位数不同怎么比位数相同怎么逐位比小数长度不一致怎么处理比较逻辑写得好不好直接影响除法试商的效率也决定了整个库的正确性。下一篇我们就从通用比较原理讲起再对照immense的比较运算符实现把六向比较的每一层逻辑都拆解得明明白白。