大数相乘，快速算法？
计算乘方是有快速算法的，并不是一个一个蛮力乘上去的。比如想算2^10000，计算机先算2^5000，再算一次平方，即两个数的乘法。而为了计算2^5000，计算机会先算2^2500再算一次平方。这个算法叫快速幂算法，对于2^N的计算，如果认为每次乘法的时间复杂度是O(1)的话，那整体的时间复杂度只有O(logN)级别。 一般来说，为了实现快速幂算法，首先把指数做二进制表示，比如你要算A的23次方，可以把23分解为16+4+2+1。然后计算B=A^2，C=B^2=A^4，D=(C^2)^2=A^16。最终结果为ABCD相乘。 但这里乘法的复杂度并不是O(1)，因为它是无限精度的，也就是所谓的大数乘法。大数乘法也有很多算法，最朴素的，类似手算的方法，复杂度是O(N^2)，其他一些方法有分治法，复杂度O(N^1.58)，FFT方法，复杂度O(N logN loglogN)等。快速幂的O(logN)次大数乘法中，最复杂的只有最后一次，也就是2^5000的那次，前面的复杂度几何级数衰减，所以整体复杂度也就是最后一次计算的复杂度。如果你用FFT方法的话，复杂度也就是比线性多了一点点，一般计算机上随便算算就出来了。 CPU没有全速运行是因为这个程序只用了1个核心在做计算，而你显示的是总的使用率，所以大概会保持在四分之一的水平。 是否用到了移位操作涉及Python大数运算的具体设计，我不是很懂就不多讲了。但原理上讲也是很有可能的，如果用比特串存储大数的话，那么计算2^N只需要在数组的第N位设置一个1，其余设置为0即可，那么转换到十进制是这段代码中最消耗计算量的部分。
快速算法指的是可以减少大数相乘运算所需的时间复杂度的一系列算法。
传统的大数相乘算法是将两个数的每一位相乘，然后按照进位规则将结果相加。这个算法的时间复杂度为O(m*n)，其中m和n分别是两个大数的位数。
快速算法包括Karatsuba算法和快速傅里叶变换（FFT）算法。
Karatsuba算法是一种分治算法，它基于一个重要的等式，即：(a+b)(c+d) = ac + ad + bc + bd。这个等式可以将一个大数相乘的问题分解为三个小数相乘的问题，并且可以通过递归的方式来解决。Karatsuba算法的时间复杂度约为O(n^log2 3)，其中n是两个大数的位数。
快速傅里叶变换（FFT）算法利用了傅里叶变换的思想，将大数相乘问题转化为多项式乘法问题。FFT算法可以将多项式乘法的时间复杂度从O(n^2)降低到O(nlogn)，进而减少大数相乘的运算时间。但是FFT算法需要进行较多的预处理和后处理步骤，因此对于小规模的大数相乘问题可能并不实用。
综上所述，Karatsuba算法和FFT算法都是常见的大数相乘的快速算法，它们能够减少传统算法的时间复杂度并提高计算效率。
大数乘法用什么算法啊？
大数乘法基本上是乘法竖式笔算的代码化。
基本功能有3个
1.大数的数组表示。
2.大数乘以小数，得到大数。
3.大数加大数，得到大数。
对于1，其实就是int数组的每个元素存储若干位。比如每个元素保存4个十进制位。[0]存储个十百千，[1]存储万、十万、百万、千万，诸如此类。一个数组保存一个大数。因此需要一个额外的int变量记录当前数组用了多少个元素（类似于字符串长度）。
对于2，“小数”指的是能用一个int保存的数。注意这里只限4个二进制位（和1里提到的位数一致）。
比如123456789这个数字，[0]保存6789，[1]保存2345，[2]保存1。长度3。
这个大数乘以小数，比如9999，过程就是[0]*9999，即6789*9999=67883211，积的低四位（%10000）3211保存到积（大数）的[0]，剩下6788的进位到[1]。
然后2345*9999=?23447655，加上刚才进位上来的6788得到23454443，其中4443保存到积（大数）的[1]中，2345进位到[2]。
