企业官网建设流程全解析

跳转链接

• 高精度计算入门与immense数据模型精讲（一）
• 高精度计算入门与immense数据模型精讲（二）
• 高精度计算入门与immense数据模型精讲（三）
• 高精度计算入门与immense数据模型精讲（四）
• 高精度计算入门与immense数据模型精讲（六）
• 高精度计算入门与immense数据模型精讲（七）
• 高精度计算入门与immense数据模型精讲（八）
• 高精度计算入门与immense数据模型精讲（九）
• immense大实数数据库

前言：乘法是高精度性能的第一道分水岭

前面我们已经吃透了加减运算，它们都是线性时间O(n)的算法，位数翻倍，耗时也基本翻倍。但乘法不一样——最朴素的竖式乘法是O(n²)，当位数从百位涨到千位、万位时，耗时会呈平方级增长，很快就会慢到无法接受。

所以，乘法算法的优劣，直接决定了一个高精度库的性能上限。工业级的GMP库用到了FFT快速傅里叶变换乘法，可以把复杂度压到接近O(n log n)；而对于教学级、工具级的库，Karatsuba分治乘法是最经典的入门优化——它用「加减法换乘法」的巧思，把复杂度从O(n²)降到了O(n^1.585)，实现不算复杂，收益却非常可观。

immense就采用了「普通竖式 + Karatsuba自动切换」的混合策略：位数低于阈值用朴素竖式，避免递归开销；位数超过阈值自动启用分治乘法，提升大数位性能。

本篇我们依然严格遵循「通用原理先行，代码实现对照」的教学节奏：先从最基础的竖式乘法讲起，一步步推导Karatsuba的算法思想、数学公式与复杂度；再讲实数乘法的小数点处理通则；最后对照immense的源码，逐函数拆解从底层移位、单数字乘法到完整Karatsuba递归、实数乘法封装的全部实现。

一、通用原理：高精度乘法的核心方法论

1.1 朴素竖式乘法：最基础的O(n²)实现

在讲优化之前，必须先搞懂最朴素的竖式乘法。它是所有高级乘法的基础，也是递归的终止条件。

前提约定

两个非负整数，倒序存储（低位在下标0）。

核心思想

和手算乘法完全一致：用第二个数的每一位，分别去乘第一个数的全部位，得到一行中间结果；每一行根据数位权重向左偏移对应位数；最后把所有行累加起来，就是最终乘积。

标准算法步骤

1. 初始化一个长度为n+m的结果数组，全部置0（两个n位和m位的数相乘，结果最多n+m位）
2. 遍历第二个数的每一位i：
   • 初始化进位carry = 0
   • 遍历第一个数的每一位j：
     • 乘积 = 第j位 × 第i位 + 结果第i+j位 + 进位
     • 结果第i+j位 = 乘积 % 10
     • 进位 = 乘积 / 10
   • 剩余进位追加到结果高位
3. 清理结果的前导零（倒序存储即清理末尾的零）

时间复杂度

双重循环嵌套，O(n×m)。如果两个数都是n位，就是O(n²)。

教学要点：为什么结果放在i+j的位置？
因为第i位代表10^{i，第j位代表10}j，相乘就是10^(i+j)，权重刚好对应结果的第i+j位。这是竖式乘法最核心的位置关系，也是所有优化算法的根基。

1.2 分治思想的引入：拆成小块算

当位数很大时，O(n²)的增长速度是灾难性的。一万位的两个数相乘，要做一亿次单位乘法，这在十进制字符串库里会非常慢。

于是人们想到了分治法：把大数拆成两半，分别算小块的乘积，再合并成最终结果。

拆分方式

把两个n位的大数x和y，都拆成高位部分和低位部分，分界点在中间第m位：

• x = x₁ × 10ᵐ + x₀ （x₁是高半段，x₀是低半段）
• y = y₁ × 10ᵐ + y₀ （y₁是高半段，y₀是低半段）

朴素分治：四次乘法

直接展开乘积：
xy = (x₁×10ᵐ + x₀)(y₁×10ᵐ + y₀)
=x₁y₁× 10²ᵐ +(x₁y₀ + x₀y₁)× 10ᵐ +x₀y₀

这里面有4个半长的乘法：x₁y₁、x₁y₀、x₀y₁、x₀y₀。
递推式是 T(n) = 4T(n/2) + O(n)，根据主定理，复杂度还是O(n²)，没有任何优化。

这就是分治的困境：拆了，但没有更快，因为乘法次数没有减少。

1.3 Karatsuba的巧思：三次乘法代替四次

1960年，23岁的Karatsuba提出了一个极其精妙的变形，用加减法换取一次乘法：

我们需要的中间项是 S = x₁y₀ + x₀y₁。
构造一个新的乘积：
(x₁ + x₀)(y₁ + y₀) = x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀

把右边整理一下：
(x₁ + x₀)(y₁ + y₀) = x₁y₁ + x₀y₀ + (x₁y₀ + x₀y₁)

所以：
x₁y₀ + x₀y₁ = (x₁+x₀)(y₁+y₀) - x₁y₁ - x₀y₀

也就是说，我们只需要算三次乘法：

1. z₀ = x₀y₀ （低位乘低位）
2. z₂ = x₁y₁ （高位乘高位）
3. z₁ = (x₁+x₀)(y₁+y₀) - z₂ - z₀ （和乘和，减去已知的两个）

最终结果：
xy = z₂ × 10²ᵐ + z₁ × 10ᵐ + z₀

四次乘法变成了三次，多了两次加法和两次减法。而加减法都是O(n)的，在n很大的时候，减少一次乘法的收益远远超过加减的开销。

1.4 复杂度推导：为什么是n^1.585

Karatsuba的递推式变成了：
T(n) = 3T(n/2) + O(n)

根据主定理（Master Theorem），对于 T(n) = aT(n/b) + f(n)：

• a=3，b=2，log_b(a) = log₂3 ≈ 1.585
• f(n) = O(n)，多项式次数低于1.585

所以时间复杂度为：
T(n) = O(n^log₂3) ≈ O(n¹·⁵⁸⁵)

这是什么概念？

• n=1000时，O(n²)是100万次操作，O(n^1.585)约为6万次，差了十几倍
• n=10000时，O(n²)是1亿次，O(n^1.585)约为390万次，差了二十多倍

位数越多，Karatsuba的优势越明显。这就是分治优化的威力。

教学要点：Karatsuba是所有快速乘法的思想源头。更快的Toom-Cook是把数拆成更多段，用更多加减法换更少乘法；FFT乘法则是转到频域做卷积，本质都是「用更便宜的运算换取乘法次数减少」。理解了Karatsuba，就能举一反三。

1.5 递归阈值：混合策略的必要性

既然Karatsuba更快，为什么不从小位数就开始用？

因为递归有开销：拆分字符串、调用函数、加减合并、移位，这些都有常数成本。当位数很少时，这些开销甚至会超过节省下来的乘法时间，反而比朴素竖式更慢。

所以工业界的通用做法是混合策略：

• 当位数小于某个阈值时，用朴素竖式乘法
• 当位数大于阈值时，启用Karatsuba分治

这个阈值没有标准答案，和实现语言、存储方式、硬件都有关系，通常在几十到几百之间。immense里定义的阈值是120：

#define IMM_KARATSUBA_THRESHOLD 120

低于120位用普通竖式，高于120位自动切换分治。

1.6 实数乘法：小数点的通用处理

前面讲的都是整数乘法，扩展到实数非常简单：

两个实数相乘，乘积的小数位数 = 两个乘数的小数位数之和。

通用处理步骤：

1. 统计两个数各自的小数位数 d1、d2
2. 把两个数的小数点全部右移，变成纯整数（相当于各自乘以10^d1和10d2）
3. 按整数乘法计算乘积
4. 把乘积的小数点左移 (d1+d2) 位，还原成实数结果

举个例子：1.23 × 4.5

• d1=2，d2=1，总小数位3
• 变成整数相乘：123 × 45 = 5535
• 小数点左移3位：5.535

这就是所有实数高精度乘法的通用范式——先整数化，相乘，再还原小数点。核心工作量都在整数乘法上，小数只是移位问题。

1.7 符号处理：同号得正，异号得负

和加减一样，乘法也遵循「符号与数值分离」的原则：

• 先取两个数的绝对值相乘
• 符号由两个数的符号共同决定：相同为正，不同为负

所以符号判断只有一行逻辑，核心运算全部针对无符号数。

二、immense 实现对照：乘法体系逐函数精讲

immense的乘法体系和加减一样，采用分层设计：

1. 底层工具层：Product_10（小数点平移）、IdProduct（单数字乘法）
2. 核心算法层：karatsuba递归函数 + 字符串辅助函数
3. 实数封装层：Product（处理小数点的实数乘法）
4. 符号调度层：Centre_P（符号中心化）
5. 上层接口层：运算符重载

我们从最底层的工具函数讲起，一路向上到完整的乘法运算符。

2.1 Product_10：小数点平移的基石

这是immense里非常有特色的一个工具函数，作用是把整个数乘以10或者除以10，等价于小数点右移或左移一位。它是实数乘除、缩放、取整等大量操作的基础。

完整源码：

immense immense::Product_10(bool positive){ if(positive){ if(this->DCMp!=""){ this->LTGp=this->DCMp[0]+this->LTGp; this->DCMp.erase(0,1); } else this->LTGp='0'+this->LTGp; } else{ if(this->LTGp!="0"){ this->DCMp=this->LTGp[0]+this->DCMp; this->LTGp.erase(0,1); } else this->DCMp='0'+this->DCMp; if(this->LTGp=="")this->LTGp="0"; } this->rationalize(); return *this; }

乘以10（小数点右移一位）

if(positive){ if(this->DCMp!=""){ this->LTGp=this->DCMp[0]+this->LTGp; this->DCMp.erase(0,1); } else this->LTGp='0'+this->LTGp; }

乘以10，所有数位左移一位，等价于小数点右移一位。

• 如果有小数部分：小数的第一位（十分位）变成整数的最低位，插到LTGp最前面
• 如果没有小数：整数末尾补零（倒序存储就是头部插零）

设计巧思：整数倒序存储，最低位在下标0；小数正序存储，最高位在下标0。所以小数点相邻的两位，刚好都是各自字符串的首字符。平移小数点，就是把一个字符从一边的头部搬到另一边的头部，极其简洁。

除以10（小数点左移一位）

else{ if(this->LTGp!="0"){ this->DCMp=this->LTGp[0]+this->DCMp; this->LTGp.erase(0,1); } else this->DCMp='0'+this->DCMp; if(this->LTGp=="")this->LTGp="0"; }

除以10，所有数位右移一位，等价于小数点左移一位。

• 如果整数不是0：整数的最低位（下标0）变成小数的最高位，插到DCMp最前面
• 如果整数是0：小数前面补零
• 最后保证整数部分非空，空了就补0

这个函数完美体现了「整数倒序 + 小数正序」存储设计的优势——小数点平移只需要操作字符串头部，一行搬运即可完成。

2.2 IdProduct：大数 × 一位数字

IdProduct计算一个高精度数乘以一个0~9的单个数字，是朴素竖式乘法的基础单元，也是后面除法二分试商的核心工具。

完整源码：

immense IdProduct(immense p,char q){ int r,carry=0; for(int i=p.DCMn-1;i>=0;i--){ r=p.DCMp[i]-'0'; p.DCMp[i]=(r*(q-'0')+carry)%10+'0'; carry=(r*(q-'0')+carry)/10; } for(int i=0;i<p.LTGn;i++){ r=p.LTGp[i]-'0'; p.LTGp[i]=(r*(q-'0')+carry)%10+'0'; carry=(r*(q-'0')+carry)/10; } p.LTGp+=char(carry+'0'); p.rationalize(); return p; }

执行流程

1. 先乘小数部分：从小数末尾（最低位）往高位乘，逐位计算，传递进位
2. 再乘整数部分：从整数低位（下标0）往高位乘，继续传递进位
3. 最终进位：全部乘完还有进位，追加到整数最高位
4. 归一化收尾

逻辑和单数字加法高度对称，只是把加变成乘，进位从「和除以10」变成「积除以10」。

2.3 Karatsuba的辅助工具：纯字符串运算

在karatsuba函数之前，immense定义了四个静态辅助函数，专门操作倒序的整数字符串，不涉及完整immense对象，轻量高效。

这三个函数就是Karatsuba算法里「加减、移位」的具体实现，逻辑和前面讲的通用加减完全一致，只是去掉了小数、符号等所有额外负担，纯为整数运算优化。

2.4 karatsuba 递归函数：分治乘法核心

这是整个乘法体系最核心的部分，完整实现了Karatsuba分治算法。我们分段拆解。

完整源码框架：

static std::string karatsuba(std::string x,std::string y){ // 1. 递归终止：低于阈值用朴素竖式 if((int)x.size()<IMM_KARATSUBA_THRESHOLD||(int)y.size()<IMM_KARATSUBA_THRESHOLD){ // 朴素竖式乘法实现 ... return r; } // 2. 拆分高低位 int n=std::max(x.size(),y.size()); int m=n/2; std::string x0=x.substr(0,m); std::string x1=(x.size()>m)?x.substr(m):"0"; std::string y0=y.substr(0,m); std::string y1=(y.size()>m)?y.substr(m):"0"; // 3. 三次递归乘法 std::string z0=karatsuba(x0,y0); std::string z2=karatsuba(x1,y1); std::string z1=str_sub(str_sub(karatsuba(str_add(x0,x1),str_add(y0,y1)),z0),z2); // 4. 移位合并 std::string res=str_add(str_add(str_shift_left(z1,m),str_shift_left(z2,2*m)),z0); return res; }

第一步：递归终止条件

if((int)x.size()<IMM_KARATSUBA_THRESHOLD||(int)y.size()<IMM_KARATSUBA_THRESHOLD){ // 朴素竖式乘法 ... }

任意一个数长度低于120位，就不再递归，直接用朴素竖式计算。这就是混合策略的阈值开关。

里面的朴素竖式实现，和我们前面讲的通用算法完全一致：双重循环，结果累加在i+j位置，处理进位，最后清理前导零。

第二步：拆分高低位

int n=std::max(x.size(),y.size()); int m=n/2; std::string x0=x.substr(0,m); std::string x1=(x.size()>m)?x.substr(m):"0";

• 取较长数的长度为基准，从中间切开
• m 是低位段的长度
• x0 是低m位（下标0到m-1），x1 是高位剩余部分
• 长度不够的高位补0

因为字符串是倒序存储的，所以前面是低位，后面是高位，substr(0,m)刚好取到低m位，和数学上的拆分完全对应。

第三步：三次乘法计算 z0、z1、z2

std::string z0=karatsuba(x0,y0); // 低位乘低位 std::string z2=karatsuba(x1,y1); // 高位乘高位 // z1 = (x0+x1)*(y0+y1) - z0 - z2 std::string z1=str_sub(str_sub(karatsuba(str_add(x0,x1),str_add(y0,y1)),z0),z2);

这三行完美对应Karatsuba的核心公式：

1. z0 = x0y0
2. z2 = x1y1
3. z1 = (x0+x1)(y0+y1) - z0 - z2

三次递归调用，其余都是加减。这就是整个算法最精妙的地方。

第四步：移位合并得到最终结果

std::string res=str_add(str_add(str_shift_left(z1,m),str_shift_left(z2,2*m)),z0);

对应公式：xy = z₂×10²ᵐ + z₁×10ᵐ + z₀

• z2 左移 2m 位（乘以10^2m）
• z1 左移 m 位（乘以10^m）
• z0 不动
• 三者相加就是最终乘积

str_shift_left就是在倒序字符串头部插零，等价于数值左移、乘以10的幂次。

教学要点：整个karatsuba函数，从阈值判断、拆分、三次乘法到移位合并，和数学推导一一对应。理解了公式，代码就是公式的直译。

2.5 Product 函数：实数乘法的完整封装

karatsuba只解决了整数乘法，Product函数负责把实数乘法转化成整数乘法，再还原小数点。

完整源码：

immense Product(immense x,immense y){ while(y.DCMp!=""){ y.Product_10(true); x.Product_10(true); } x.rationalize(),y.rationalize(); int rd_DCM_length=x.DCMn; immense result; std::string raw=karatsuba(x.LTGp,y.LTGp); result.LTGp=raw; result.DCMp=""; result.rationalize(); while(rd_DCM_length!=0){ result.Product_10(false); rd_DCM_length--; } result.rationalize(); return result; }

执行流程

1. 整数化处理：循环把y的小数全部移到整数部分，x同步移位。每移一位，相当于两个数都乘以10，乘积不变。
2. 记录总小数位：移位完成后，x的小数位数就是两个数原来的小数位数之和，记下来后面还原用。
3. 整数相乘：调用karatsuba计算两个整数部分的乘积。
4. 还原小数点：把结果除以10^rd_DCM_length，也就是循环调用Product_10(false)，左移对应位数。
5. 归一化收尾

完全对应「整数化 → 相乘 → 还原小数点」的通用实数乘法流程。

2.6 Centre_P：符号中心化调度

和加减的Centre_AL一样，乘法也有中心化函数，负责分离符号与数值。

immense Centre_P(immense x,immense y){ immense result; bool Rsymbol=(x.symbol==y.symbol); x.abs(),y.abs(); result=Product(x,y); result.symbol=Rsymbol; return result; }

逻辑极其简洁：

• 符号由两者是否相同决定：同号为正，异号为负
• 取绝对值，调用无符号乘法Product
• 给结果回填符号

这就是「符号与数值分离」设计的标准范式。

2.7 运算符层：接口封装

上层的乘法运算符全部复用Centre_P：

inline immense immense::operator*(const immense other)const{ immense t=other; return Centre_P(*this,t); } inline void immense::operator*=(const immense other){ immense t=other; *this=Centre_P(*this,t); }

和加减运算符结构完全一致，分层清晰，逻辑零冗余。

三、拓展：性能权衡与常见坑点

3.1 什么时候Karatsuba真正划算

• 百位以内：朴素竖式更快，递归开销占主导
• 千位级别：Karatsuba优势明显，通常快3~5倍
• 万位以上：差距进一步拉大，此时更优的选择是FFT乘法

immense把阈值设为120，是十进制字符串实现下比较合理的平衡点。

3.2 设计权衡点评

1. 十进制Karatsuba
   • 优点：实现直观，调试方便，和手算逻辑一致
   • 缺点：单字符存一位，空间利用率低，运算速度不如二进制limb实现
   • 定位：教学与中小规模计算，可读性优先于极限性能
2. 值传递递归
   karatsuba函数用值传递字符串，递归过程中会产生大量字符串拷贝。
   • 优点：代码简洁，不用管理内存
   • 缺点：有额外的拷贝开销
   • 这也是教学级实现的典型取舍：用少量性能换取代码简洁易懂
3. 自动阈值切换
   小数用竖式、大数用分治，兼顾了小数据的低开销和大数据的高性能，是工程上的最佳实践。

3.3 常见坑点盘点

实现Karatsuba乘法，新手最容易踩这几个坑：

1. 拆分边界错误
   • 倒序存储时低位在前，拆分方向不能搞反
   • 长度不足时高位要补零，不能直接返回空串
2. z1减法的借位问题
   • 理论上(x1+x0)(y1+y0)一定大于等于x1y1+x0y0，但实现中如果加法处理不当，可能出现减法不够减的情况
   • 必须保证减法的被减数大于减数
3. 移位位数错误
   • z1移m位，z2移2m位，位数错一位结果就完全不对
   • 倒序字符串的移位是头部插零，方向不能搞反
4. 实数小数位数累加错误
   • 两个数小数位数之和才是总小数位，移位次数不能算错

3.4 自我验证练习

可以用简单案例手算一遍，对照代码逻辑验证理解：

1. 12 × 34拆成 m=1：x0=2, x1=1；y0=4, y1=3
   • z0 = 2×4 = 8
   • z2 = 1×3 = 3
   • z1 = (1+2)(3+4) - 3 - 8 = 21 - 11 = 10
   • 结果 = 3×100 + 10×10 + 8 = 408，正确
2. immense("1.5") * immense("2.4")→ 整数化15×24=360 → 小数点左移2位 → 3.6

四、本篇小结与下篇预告

4.1 核心知识点回顾

通用原理部分：

1. 朴素竖式乘法是O(n²)，核心是i+j位的权重对应关系
2. Karatsuba分治用三次乘法代替四次，加减法换乘法，复杂度降到O(n^1.585)
3. 混合策略：低于阈值用朴素竖式，高于阈值用分治，平衡递归开销与性能
4. 实数乘法 = 整数化 + 整数乘法 + 小数点还原，总小数位数相加
5. 符号规则：同号得正，异号得负

实现对照部分：

1. Product_10利用存储结构优势，用字符搬运实现小数点平移
2. IdProduct实现单数字乘法，是竖式与试商的基础
3. karatsuba完整实现分治递归：阈值判断 → 拆分高低位 → 三次乘法 → 移位合并
4. Product封装实数乘法流程：去小数点 → 整数相乘 → 还原小数点
5. Centre_P做符号中心化，运算符层统一调用

4.2 下篇预告

乘法之后，自然是除法。如果说乘法还有Karatsuba这样的经典优化，那么除法就是高精度里公认最复杂、最考验功底的模块——试商、对齐、余数迭代，每一步都藏着细节。

immense的除法采用的是长除法 + 二分试商的经典方案：每一位商在0~9之间二分查找，用比较运算判断试商是否合适，逐位算出结果。

下一篇我们就来讲除法：先讲高精度除法的通用原理、试商的几种方法、实数除法的小数点处理；再对照Division、Centre_D等函数，逐段拆解长除法的完整实现逻辑。除法是四则运算的收官之作，也是后面幂根、超越函数的重要基础。