【大数处理】原理探析及模拟实现
Hello, 各位勇敢的小伙伴, 大家好, 我是你们的嘴强王者小五, 身体健康, 脑子没病.
本人有丰富的脱发技巧, 能让你一跃成为资深大咖.
一看就会一写就废是本人的主旨, 菜到抠脚是本人的特点, 卑微中透着一丝丝刚强, 傻人有傻福是对我最大的安慰.
欢迎来到 小五 的 随笔系列 之 【大数处理】原理探析及模拟实现.
前言
0.1+0.2=0.300000000000000040.1 + 0.2 = 0.300000000000000040.1+0.2=0.30000000000000004，一个大家刚入门前端时就会接触到的问题，原因是小数精度丢失
实际工作中，我们会引入诸如 big.js 的库来做相应处理，那大家有没有探索过这类库是怎么实现的呢？如果没有，不妨跟着笔者的步伐，一行一行的敲出一个属于自己的大数处理库
tips：本文仅实现 “加减乘除” 四个基本操作，其余操作大同小异，感兴趣的话大家可自行实现
数据构造
核心思路： 将数字转换为十以内整数的加减法运算，这样既不存在小数点精度问题，也不存在范围超出问题，进而实现了大数处理。
存储格式： Big {sign: 1, pow: 2, data: [1, 2]}
👉 以120为例
-
sign：正负号，1代表正数，-1代表负数
- 120为正数，故sign为1
-
pow：幂，默认为0
- 120=1.2∗102120 = 1.2 * 10^2120=1.2∗102，故pow为2，这里底数应 1<=n<101<=n<101<=n<10（0除外）
-
data：数据
- 拆解数字存入数组，并抹掉首尾的零，得到 [1,2][1, 2][1,2]
数据处理：
鉴于 signsignsign 和 datadatadata 的逻辑都比较简单，我们先思考一下 powpowpow 的逻辑
👉 我们穷举一些例子做观察：
- 120=1.2∗102⇒pow=2120 = 1.2 * 10^{2} \Rightarrow pow = 2120=1.2∗102⇒pow=2
- 12.12=1.212∗101⇒pow=112.12 = 1.212 * 10^{1} \Rightarrow pow = 112.12=1.212∗101⇒pow=1
- 1.2=1.2∗100⇒pow=01.2 = 1.2 * 10^{0} \Rightarrow pow = 01.2=1.2∗100⇒pow=0
- 0.012=1.2∗10−2⇒pow=−20.012 = 1.2 * 10^{-2} \Rightarrow pow = -20.012=1.2∗10−2⇒pow=−2
👉 可以发现如下规律：
-
整数的 powpowpow 即为
str.length - 1 -
小数的 powpowpow 则取决于小数点的位置，每向后移一位
pow++，每向前移一位pow--
👉 特殊处理 -- 科学计数法
12.37e−2=12.37∗10−212.37e^{-2} = 12.37 * 10^{-2}12.37e−2=12.37∗10−2，我们只需找到 e 的位置，e 前的数字按上述处理，e 后的数字为需要额外追加的幂
🦥 翠花上代码
数据还原：
数据还原则是对数据处理的逆向操作，通过 powpowpow 和 data.lengthdata.lengthdata.length 即可确认下述内容
- pow<0pow < 0pow<0，⇒\Rightarrow⇒ 待还原的数字小于1，向头部补零并追加小数点
- pow>=0pow >= 0pow>=0
- pow>=data.lengthpow >= data.lengthpow>=data.length，⇒\Rightarrow⇒ 整数，按需向尾部补零
- pow<data.lengthpow < data.lengthpow<data.length，⇒\Rightarrow⇒ 小数，追加小数点
🦥 翠花上代码
加
32.79+0.1232.79 + 0.1232.79+0.12，我们图解一下它的运算过程
原理：逐位相加，有进位加进位
说明：
-
符号相反 ⇒\Rightarrow⇒ 减法，eg：3+(−2)=3−2eg：3 + (-2) = 3 - 2eg：3+(−2)=3−2
-
通过 powpowpow 对齐位数
-
若最后仍有进位，需处理进位，eg：9+8=17eg：9 + 8 = 17eg：9+8=17
-
注意我们的约定格式，若结果数据 datadatadata 前后有多余的零，需处理
🦥 翠花上代码
减
32.91−0.1232.91 - 0.1232.91−0.12，我们图解一下它的运算过程
原理：逐位相减，有借位减借位
说明：
-
减法中被减数应大于减数，eg：2−3⇒−(3−2)eg：2 - 3 \Rightarrow -(3-2)eg：2−3⇒−(3−2)，相等则直接返回 000
-
符号相反 ⇒\Rightarrow⇒ 加法
- 2−(−2)=2+22 - (-2) = 2 + 22−(−2)=2+2
- −2−2=(−2)+(−2)-2 - 2 = (-2) + (-2)−2−2=(−2)+(−2)
-
注意我们的约定格式，若结果数据 datadatadata 前后有多余的零，需处理
🦥 翠花上代码
乘
32×6932 × 6932×69，我们图解一下它的运算过程
原理：乘法即加法，逐位相乘，逐位相加
说明：
-
若相乘的两数中有零，直接返回零
-
两数字相乘的最大位数是 data1.length+data2+lengthdata1.length + data2+lengthdata1.length+data2+length，最大幂是 pow1+pow2+1pow1 + pow2 + 1pow1+pow2+1
-
按位相乘后，写入对应位置，并做加法处理
-
处理结果数据 datadatadata 首尾的零
🦥 翠花上代码
除
2208÷692208 ÷ 692208÷69，我们图解一下它的运算过程
原理：除法即减法，逐次相减，记录次数
说明：
-
除数不能为零
-
被除数为零，直接返回零
-
幂为被除数的幂减除数的幂，若被除数小于除数，则借位减一
-
dp⇒dp \Rightarrowdp⇒ 小数点后的保留位数，假设 dp=8dp = 8dp=8，20÷3⇒2,000,000,000÷320 ÷ 3 \Rightarrow 2,000,000,000 ÷ 320÷3⇒2,000,000,000÷3
-
减法运算调用前面已实现的
minus方法 -
处理结果数据 datadatadata 首尾的零
🦥 翠花上代码
