大整数乘法 1.算法原理 如果我们想要计算两个较大的数字相乘的时候,由于计算机硬件限制可能无法计算,因此我们可以将每个乘数用加法和乘法做分解,当分解到每个因子只是一位数的时候,乘法就很简单了,这也是一种分治法。 (1)分解:首先将2个大整数a(n位)、b(m位)分解为两部分: ah al bh bl 然后, 其中ah、al为n/2位,bh、bl为m/2位。两个大整数a、b相乘转换成了4个乘法运算,而乘数的位数变为了原来的一半。 (2)求解子问题。继续分解每个乘法运算,直到分解有一个乘数为1位数时停止分…