高精度计算

see: https://www.bilibili.com/list/watchlater?oid=517533957&bvid=BV19g411i7Lj

采用数组分离进制和数位表示大数，无表示上限，按下述规则进行四则运算。

进制转换

$X_{(N)}=\overline {a_n\cdots a_1a_0}=\sum \limits_{i=0}^n{a_i\cdot N^i}$

数位上的数字若大于进制，则向前进位，若为负数，则置为正数，向前递补。 例如100进制：

109809(10) = [10]  [98]  [09]
             100^2 100^1 100^0

转换成100进制下的3位数，数组长度也为3。

基础运算

加减法

1. 直接各个数位对应的数字相加减
2. 从低位往高位，统一处理进位和退位

乘法

将一个数的各个数位上的数依次与另一数相乘，再把结果相加。

$$\overline {a_n\cdots a_0} \times \overline {b_m\cdots b_0}=\sum_{i=0}{a_i\cdot \overline {b_m\cdots b_0} \cdot N^{i}}$$

矩阵运算相乘：

$$N = \begin{bmatrix} a_n \\ a_{n-1}\\ \vdots\\ a_0 \end{bmatrix} \times \begin{bmatrix} b_m & b_{m-1} & \cdots & b_0 \end{bmatrix} \\ W = \begin{bmatrix} N^n \\ N^{n-1}\\ \vdots\\ N^0 \end{bmatrix} \times \begin{bmatrix} N^m & N^{m-1} & \cdots & N^0 \end{bmatrix} \\ N: n \times m\\ W: n \times m\\$$

把 $N$ 每条副对角线元素相加，得到的矩阵即为结果矩阵。 把 $N$ 和 $W$ 做点乘，再把所有元素相加，即得到结果数值。

除法

1. 从最高位除起
2. 如果余数大于除数，则相减。循环这个过程，记录相减的次数，即为当前数位上的商。
3. 如果余数小于除数，且仍有数位，则拼接数位上的数到余数末尾，执行步骤2。

• 在步骤2，使用如二分查找等算法，快速定位最多的相减次数（即商）。