乘积位数上界的证明

作者: M_lear | 来源:发表于2019-07-16 14:48 被阅读0次

乘积位数上界的证明
泛化误差上界证明：
java算法巩固训练day02
2018-06-20 479. Largest Palindro
Thinking in Java第四章练习10
欧拉计划4（最大回文乘积）
小学速算
Python|Numpy聚合
吸血鬼数字
吸血鬼数字

先说要证明的结论：同进制下，一个 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。

乘积位数上界的证明
先说要证明的结论：同进制下，一个 m 位的数乘一个 n 位的数，乘积不超过 m+n 位。证法一：下面用多项式表...
泛化误差上界证明：
揭示了，训练误差小的模型，其泛化误差也会小
java算法巩固训练day02
乘积最大给出一个n位数，在数字中间添加k个乘号,使得最终的乘积最大。非记忆化版本！！！记忆化搜索版本：定义d...
2018-06-20 479. Largest Palindro
题意：给你一个数n，1 <= n <= 8，代表n位数，返回由2个n位数乘积组成的最大回文数，并mod 1337。...
Thinking in Java第四章练习10
Thinking in Java第四章练习10 我的解题思路就是轮询所有的2位数组合，比较乘积和这对数字的各位数的...
欧拉计划4（最大回文乘积）
题目最大回文乘积回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = ...
小学速算
不管是什么样的二位数乘以11，乘积的百位和个位数字会是被乘数的两个数字，而十位数字则是被乘数的数字相加
Python|Numpy聚合
当面对大量数据时，第一步通常是计算相关数据的统计值。如平均值、标准差、乘积、中位数、最小值、最大值、分位数等等。 ...
吸血鬼数字
吸血鬼数字是指位数为偶数的数字，可以由一对数字相乘而得到，而这对数字各包含乘积的一半位数的数字，其中从最初的数字中...
吸血鬼数字
吸血鬼数字指，位数为偶数，可以由一对数字相乘得到，且这对数字各包含乘积的一半位数的数字。其中，从最初的数字中选取的...

乘积位数上界的证明

证法一：

证法二：

相关文章

乘积位数上界的证明

泛化误差上界证明：

java算法巩固训练day02

2018-06-20 479. Largest Palindro

Thinking in Java第四章练习10

欧拉计划4（最大回文乘积）

小学速算

Python|Numpy聚合

吸血鬼数字

吸血鬼数字

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读