乘积位数上界的证明

2019-07-16 本文已影响0人 M_lear

先说要证明的结论：同进制下，一个 m 位的数乘一个 n 位的数，乘积不超过 m+n 位。

证法一：

下面用多项式表示 x 进制的数，数 a 有 m 位，数 b 有 n 位：
$a=\sum_{i=0}^{m-1}a_ix^i(0\le a_i<x,a_i\in N,a_{m-1}\ne 0)$
$b=\sum_{i=0}^{n-1}b_ix^i(0\le b_i<x,b_i\in N,b_{n-1}\ne 0)$
根据多项式的乘积运算可得： $a\cdot b=\sum_{i=0}^{m-1}\sum_{j=0}^{n-1}a_ib_jx^{i+j}$
因为这个结果并没有进位，所以看不出两数积的位数，但可以知道至少有 m+n-1 位。

现在考虑 a，b 都取最大值的情况，其乘积结果也是最大的，此时取最大位数：
令 $a=\sum_{i=0}^{m-1}(x-1)x^i,b=\sum_{i=0}^{n-1}(x-1)x^i$
易知： $a\cdot b<(a+1)\cdot b$
而 $(a+1)\cdot b=x^m\cdot \sum_{i=0}^{n-1}(x-1)\cdot x^i=\sum_{i=0}^{n-1}(x-1)\cdot x^{m+i}$

容易看出 $\sum_{i=0}^{n-1}(x-1)\cdot x^{m+i}$ （不存在进位问题）是一个 m+n 位的数，所以一个 m 位的数乘一个 n 位的数，乘积不可能超过 m+n 位。

证法二：

首先有不等式成立： $\lfloor a\rfloor+\lfloor b\rfloor\le \lfloor a+b\rfloor\le \lfloor a\rfloor+\lfloor b\rfloor+1$
而一个 x 进制的数 a，其位数为 $\lfloor{\log_x}^a\rfloor+1$ 。
假设有 $c=a\cdot b$ ，a 的位数为 m，b 的位数为 n。
数 c 的位数为 $\lfloor{\log_x}^c\rfloor+1=\lfloor{\log_x}^{a\cdot b}\rfloor+1=\lfloor{\log_x}^a+{\log_x}^b\rfloor+1$
由上面的不等式可得 $\lfloor{\log_x}^a+{\log_x}^b\rfloor+1\le\lfloor{\log_x}^a\rfloor+1+\lfloor{\log_x}^b\rfloor+1$
又 $\lfloor{\log_x}^a\rfloor+1=m,\lfloor{\log_x}^b\rfloor+1=n$
所以乘积 c 的位数不超过 m+n。

乘积位数上界的证明

证法一：

证法二：

猜你喜欢

热点阅读