这里只是随便写的一些很短的思路和想法,也算是用做分享吧。

上次海风软件部培训,部长在讲高精度算法的时候,乘法的核心代码有一句就是:
c [ i+j ] = a [ i ] × b [ j ] ; (a,b 为两个存因数的数组,而 c 数组为储存结果的数组 )
然后学长的学长让我们思考一下“ c 中的第 i 位是由 a b 中的哪些位得来的 ”。具体的话我也记不清楚了,反正我觉得他的应该是下面我说的这个事情的这个意思。

假设两个数: A=anan1an2...a2a1a0¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯B=bmbm1bm2...b2b1b0¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
那么,设 x=10。
这时:

A=(anxn+an1xn1+...+a2x2+a1x+a0)

B=(bmxm+bm1xm1+...+b2x2+b1x+b0)

C=A×B

C=(ckxk+ck1xk1+...+c2x2+c1x+c0)(ck10xAB)
那么,显然, AB 中的项任意两个都进行一次组合(相乘),都可以得到 C 里的一项。那么可能得到 C 中的 ctxt 项的 AB 中两项的组合,一定是: aixibjxj=aibjxi+j (i+j=t)。
所以:

ct=i=0taibti

这也就是说,对于乘积 C 的第 t 位,在不考虑满十进位的情况下,都是由”两个因数 ABt
这么说好绕嘴啊,反正就是,比如 C 中的第 i 位上的数,就是由: A 中的第0位乘 B 中的第 i 位 + A 中的第1位乘 B 中的第 i-1 位 + … + A 中的第 i-1 位乘 B 中的第 1 位 + A 中的第 i 位乘 B 中的第 0 位”得来的。