大数相乘

2019-09-27 本文已影响0人 areece

两个大数相乘，这两个大数分别是a和b，现在分割成两部分，每一部分都是N位，假设是10进制的，其实对于2进制也同样适用。
$a = (a_0 * 10^N + a_1)$
$b = (b_0 * 10 ^N + b_1)$
$a * b = a_0 * b_0 * 10^{2N} + a_1 * b_1 + (a_0 * b_1 + a_1 * b_0) * 10^N$
大数乘法能够减少运算量，在于
$(a_0 + a_1) * (b_0 + b_1) = a_0*b_0 + a_1*b_1 + (a_0*b_1 + a1 * b_0)$
所以现在只用算三个乘法式，再加上一点加减运算，就可以了。
$k_1 = a_0 * b_0, k_2 = a_1 * b_1, k_3 = (a_0 + a_1) * (b_0 + b_1) - k_1 - k_2$
整个计算结果就是
$a*b = k_1 * 10 ^ {2N} + k_2 + k_3 * 10 ^ N$

大数相乘

猜你喜欢

热点阅读