谷歌提出“超大数相乘”算法，量子版递归有望成真！( 五 )_图1

图5/8

如何快速地将两个大数相乘(Lucy Reading-Ikkanda/Quanta Magazine)

数千年来，将两个n位的数字相乘，需要n2个步骤。1960年，俄罗斯数学家Anatoly Karatsuba提出了一种更好的方法。

比如，在25×63这个算式中，使用小学乘法方法需要4个单位数乘法步骤，并将4步所得的积相加，才能得到最后的结果。

同样的算式使用Karatsuba的方法，只需要做3次乘法，以及少量的加法操作和移位操作。

随着数字位数的增加，Karatsuba方法可以重复使用，将大的数字分割成较小的数字，从而节省更多的单位数乘法操作。

类似“尾调用优化”，量子版“递归算法”或将实现！

经典计算机运行Karatsuba方法时，它会随着运行进行而删除信息。例如，在将两位数重组为四位数之后，它会忘记之前的两位数，只关心四位数本身。经典的Karatsuba方法就像登山者在上山的路上脱下装备一样——不需要一路携带所有东西时，你可以走得更快。

谷歌提出“超大数相乘”算法，量子版递归有望成真！( 五 )