// 2020/06/10 修正 HTML 代码
压位高精度的写法
之前有单位高精度算法,那么有没有可以加速、节省空间的做法呢?
有!
以前,存数字数组里面只存着一个数字,所以加减都是一位一位地加,进位也是一位一位地实现。
所以,我们尝试着将数字序列从一位变成多位。
比如高精度加法:
如果压两位,我们就两位两位地存数字,运算时依然可以正常相加,但是相加的次数减半了;
进位时,只需要将进位的数字除以 $10^2$,加到下一位就可以了。
所以,如果我们压八位(保证 LL 存的下的情况),那么时空复杂度的常数是 $frac{1}{8}$。
如,计算:$13134987124987+192837918479$。
传统做法:
Step 1: 分离数位
1 3 1 3 4 9 8 7 1 2 4 9 8 7 + 1 9 2 8 3 7 9 1 8 4 7 9
Step 2: 每位相加
1 3 1 3 4 9 8 7 1 2 4 9 8 7
+ 1 9 2 8 3 7 9 1 8 4 7 9
————————————————————————————————————————————
1 3 2 12 8 17 11 14 10 3 12 13 15 16
Step 3: 进位
1 3 1 3 4 9 8 7 1 2 4 9 8 7
+ 1 9 2 8 3 7 9 1 8 4 7 9
————————————————————————————————————————————
1 3 3 2 7 8 2 5 0 4 3 4 6 6
所以答案为 $13327825043466$。
压位做法(压 $4$ 位):
Step 1: 分离数位
13 1349 8712 4987 + 1928 3791 8479
Step 2: 相加
13 1349 8712 4987
+ 1928 3791 8479
————————————————————————————————
13 3277 12503 13466
Step 3: 进位
13 1349 8712 4987
+ 1928 3791 8479
————————————————————————————————
13 3278 2504 3466
所以答案为 $13327825043466$,和上面答案一样
排坑
我们发现,有些数位进位之后会发生一些意想不到的结果:
例子:1598 + 9144
我们如果压 4 位,结果是:
1598
+ 9144
————————————————
1 0472
但是,这个 0472 如果直接输出,是 472,于是就 WA 了。
所以可以这么写:
printf("%.4d", a);
这句话的作用是如果 a 不到 4 位就把不到的位用 0 填充后输出。
但是,又有一个坑:
最高位所在的那段不能用 $0$ 填充 。
所以比较好的做法,是先输出第一个数,再按照如上填充方式输出。
压位高精度在乘法等复杂度较高的运算会有很大用处。