【大数处理】原理探析及模拟实现

Hello, 各位勇敢的小伙伴, 大家好, 我是你们的嘴强王者小五, 身体健康, 脑子没病.

本人有丰富的脱发技巧, 能让你一跃成为资深大咖.

一看就会一写就废是本人的主旨, 菜到抠脚是本人的特点, 卑微中透着一丝丝刚强, 傻人有傻福是对我最大的安慰.

欢迎来到 小五 的 随笔系列 之 【大数处理】原理探析及模拟实现.

前言

0.1+0.2=0.300000000000000040.1 + 0.2 = 0.300000000000000040.1+0.2=0.30000000000000004，一个大家刚入门前端时就会接触到的问题，原因是小数精度丢失

实际工作中，我们会引入诸如 big.js 的库来做相应处理，那大家有没有探索过这类库是怎么实现的呢？如果没有，不妨跟着笔者的步伐，一行一行的敲出一个属于自己的大数处理库

双手奉上代码链接【Github - ajun568】

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 首尾的零

🦥 翠花上代码