乘法算法

有a,b两个正整数，a除以2，b乘以2；一直除到a=1，把所有当a为奇数时，b的结果相加，其加得的结果记为x，求证x=a*b，（当a为小数时保留整数）

证明:
开始时,A1分两种情况,要么是偶数,要么是奇数,
假定为偶数记作A1=2*N1,B1=某一整数M,则
经过一次操作后变为A2=N1,B2=2M,
A1=2*N1,B1=M接着往下操作和从A1'=N1,B1'=2M开始操作最后要证明的结果是相同的,都是要证明x=A1*B1或者x=A1'*B1',显然A1*B1=A1'*B1',于是我们想的再简单一些,如果经过一次操作之后发现A仍然是偶数,那么我们虽然进行了操作但是不记录这次操作,直接在对A除以2,对B乘以2,直到A为奇数再进行记录,
换句话说,如果A1不是奇数,我们可以对A1进行多次操作后直到该数字变成奇数,然后将这个数字记作A1,不影响要证明的结论.
对应着
例子
{A1=290,B1=4}
{A2=145,B2=8}
{A3=72,B3=16}
{A4=36,B4=32}
{A5=18,B5=64}
{A6=9,B6=128}
{A7=4,B7=256}
{A8=2,B8=512}
{A9=1,B9=1024}
要证明{8, 128, 1024}三数之和等于290×4=1160
就可以记作
{{A1=145,B1=8}, {A2=9, B2=128}, {A3=1, B3=1024}}
就相当于证明{8, 128, 1024}三数之和等于145×8=1160
A1*B1=(2A2+1)*B1=2A2*B1+B1=A2*(2B1)+B1=A2*B2+B1,
同理可得
A2*B2=A3*B3+B2,
依次类推:假定共有n项,则An=1,最后一项个等式为
A[n-1]*B[n-1]=An*Bn+B[n-1]=Bn+B[n-1],
然后将n-1个等式左右分别相加,交叉消去相同项得 <