# NNA加法理论

## 概念
$a$：即第一个NNA数组。
$b$：即第二个NNA数组。
$r$：返回的NNA数组。
$c$：指的是进位。
$t$：指的是某位的含义。

## 证明方法
递归、边界值讨论、分类讨论

## 证明
### 如果没有进位
我们获取到了$a_i$,$b_i$，**如果我们直接相加是得不到正确的结果的**。因为内存中的值并不是这位的含义，这一位的含义$t_i=(n_i+1)L^i$，而不是$t_i=n_iL^i$。所以对于结果的那一位的数值$r_i$，我们应当保证$t_{ai}+t_{bi}=t_{ri}$，即$(a_i+1)L^i+(b_i+1)L^i=(r_i+1)L^i$，化简整理得$a_i+b_i+1=r_i$。**我们需要返回的$r_i$其实是$a_i+b_i+1$而不是$a_i+b_i$**。
### 如果有进位
但是我们发现，$r_i$可能会大于等于$L$，这就不符合位满足的条件了。计算一下$r_i$的取值范围，在$[1,2L)$之内，明显超出了限制，这就是**溢出**。因此我们要递归到有进位的情况。
因此我们需要引入进位，将超出的部分移到下一位处理。在数学上，这一操作本质上是将$r_i$除以$L$得到商和余数。之所以计算机科学中**只需要获取溢出的高字节部分或判断是否溢出就行了**，就是因为溢出也有范围。在这里，最大的进位为1,所以只需要布尔值存储就行了？
### 进位危机
**完全不是！**因为可能会递归到需要加上进位的情况。
我们假设获取到了$a_i$,$b_i$和$c_{i-1}$（即上一位的进位，第一位的前一位进位为0），那么为了使$t_{ai}+t_{bi}+c_{i-1}L^i=t_{ri}$，我们需要保证$a_i+b_i+c_{i-1}+1=r_i$。这次$c_{i-1}$的范围在$[0,2)$内，那么此时$r_i$的取值范围就在$[1,2L+1)$之内了。我们提到过，进位的本质其实是取商或余数，那么**这种时候进位就可能达到2了**，因此我们还要递归进位可能为2的情况。
### 还有危机吗？
我们讨论$c_{i-1}$可能为2的情况。还是获取$a_i$,$b_i$和$c_{i-1}$，但不同的是，这次$c_{i-1}$的范围是$[0,3)$。我们得到$r_i$的范围是$[1,2L+2)$，**进位最多还是2**.因此到了2就稳定了，不用递归了。因为$c$的范围是$[0,3)$，**所以我们不能用布尔值表示进位，可以用更宽的`u8`等类型表示**。
### 只有一方有数
那么你可能会好奇，如果两个输入的NNA长度不同，当遇到只有一方有数时又该如何计算和求范围呢？我们假设那个数位的值为$n_i$，那么$t_{ni}=(n_i+1)L^i$。那么为了$t_{ni}+c_{i-1}L^i=r_{ni}$，我们需要$n_i+c_{i-1}+1=r_i+1$，最终得到$n_i+c_{i-1}=r_i$。所以**需要返回的$r_i$其实就是输入与进位的相加了**。而且因为$c \in [0,3)$，得出来的范围在$[0,L+2)$之内，这位的进位反而限制在0或1之间了。所以**完全不用更改$c$的取值范围**。
### 两方都没有数
如果两方都没有数，那就只能说明遍历完了。此时不要忘了处理进位。假设上一位的进位为$c_{i-1}$，那么，为了使$c_{i-1}L^i=t_{ri}$，$c_{i-1}-1=r_i$，说明我们需要将$c_{i-1}$减去1并返回。那么如果$c_{i-1}=0$呢？减了之后不就是$-1$了吗？其实$-1$作为`Limb`也有作用，它的含义$t_{-1}=(-1+1)L^i=0$，这就相当于没有加。所以**NNA结尾的数位如果为-1，那么其实就是没有这些位**，我们直接结束遍历就行。
