将n位整数平方与两个n位整数相乘的区别

Question

免责声明：这是一道作业问题。我正在寻求提示...

F. Lake教授告诉他的学生，平方一个n位整数比将两个n位整数相乘要渐进地更快。他们应该相信他吗？

我认为通过移位/加法乘以两个n位int是一个O(n)操作，但我不知道为什么平方一个n位int会有所不同。我错过了什么吗？

- Student

---

移位和加法操作都是O(n)。由于将两个n位数相乘需要n次移位/加法操作，因此乘法的时间复杂度为O(n^2)。 - Gabe

请参阅相关的快速大数平方计算。 - Spektre

Answer 1

既然你只想要一个提示，那么答案就来自于这个公式：(a + b)^2 = a^2 + b^2 + 2*a*b

为了不破坏谜题的乐趣，我已经将完整的解决方案单独发布在这里 :)

- Nikita Rybak

---

好好研究这个方程式。在我看来，它太明显了，让这个问题变得太容易了...但也许是因为我已经知道答案了，所以才会这么想。 - Dragontamer5788

Answer 2

想象一下，平方实际上是渐近更快的。那么如果你有 a * b，你可以计算：

a = m + n
b = m - n

然后解决这个方程组给出：

m = (a+b)/2
n = (a-b)/2

但是我们有

a * b = (m+n)*(m-n) = m² - n²

或者没有中间变量：

a * b = ((a+b)² - (a-b)²)/4

所以你可以用两个平方操作替换任何乘法（还有一些加法和除以 4 的操作，这只是一个位移，对于渐近复杂度来说，这些都可以被忽略）。因此，乘法的复杂性最多是平方的两倍。当然，“两倍”是一个常数因子，这意味着两个操作具有相同的 渐近 复杂度。

- Landei

Answer 3

这是一个提示。

这是我的解决方案，使用秘密代码：Fdhnevat zrnaf lbh bayl unir gb qb bar vavgvny SG，abg gjb，fb vg'f snfgre。

- mtrw

Answer 4

改写：在将两个n位数相乘的过程中，我所能看到的唯一改进就是将一个n位数平方。这种方法可能不会在计算机科学中常用的O(n^2)与O(n)的渐进复杂度方面有显著提升。但是，如果我们按照渐进复杂度的字面意思来理解（包括乘法常数），那么这种方法确实符合该定义。总之，这是我所能想到的唯一方法，接受或者放弃都由你决定。

假设我们有两个N位数x和y。我们可以使用移位加法方法进行乘法运算（x*y），需要A*N^2 + O(N)次操作，其中A是一个常数。对于足够大的N，第二项O(N)可以忽略不计，因此操作次数基本上为A*N^2。

现在我们来计算x的平方。如果我们定义a只有x的前N/2位设置为1，b只有x的后N/2位设置为1，则

x = a + b

x^2 = (a + b)^2 = a^2 + b^2 + 2*a*b

然而请记住，我们可以用A*N^2次操作来乘以一个N位数。要将a*a相乘，我们只需进行A*(N/2)^2 = A*N/4次操作。对于b*b和a*b也是如此。如果我们忽略O(N)次操作，那么x^2 = (a + b)^2就可以在这些操作中计算出来。

A*N^2/4 + A*N^2/4 + A*N^2/4 = (3/4)*A*N^2

对于乘法计算两个任意 N 位数的标准 A*N^2 方法，我们可以使用更好的操作，仅需执行 A*N^2/4 次运算。而且，我们还可以通过重复执行相同的操作使用 a^2 和 b^2 进一步提高效率。但在某个点上继续这样做就没有太大的益处了。虽然这不是非常巨大的改进，但这已经是我能发现的全部了。你们可以自行判断这是否有所作用。

- Justin Peel

---

尽管我意识到，只有在考虑两个数字相乘的O(n^2)方法时才能看出它只是一种改进。 - Justin Peel

如果教授是正确的，那么就有一个算法可以计算满足上述要求的数字的平方（渐进地比任何两个任意数字相乘的算法都要快）。它在哪里？ - Nikita Rybak

@Nabb 渐进快并不一定意味着巨大的加速（O(n^2)与O(n)相比）。例如，前段时间出现的双轴快速排序仍然是O(N log N)，但其系数在渐进上较小。换句话说，对于足够大的N，双轴快速排序更快。这里也是一样的。渐进快只是意味着当N趋近无穷时它更快。至少，这是我一直理解的。通常情况下，当人们谈论渐进快时，他们指的是O(N)与O(N^2)之间的差异。按照这个定义，我的解决方案失败了。 - Justin Peel

教授显然是错的：如果您看一下我的答案，就会发现一个乘法可以转换为两个平方操作，因此渐近复杂度是相同的。 - Landei

@Landei @Nikita 请阅读我的重写解决方案。希望你们至少能理解我想要展示的内容。也许你们不认为这是足够好的改进，但希望你们至少能理解它。它也没有反驳Landei的说法，因为平方两个数字并减去结果并不比直接乘法更快。 - Justin Peel

Answer 5

考虑计算机完成这些任务所需的步骤。记住，计算机的工作方式与人类截然不同。

- Frank V

---

要将两个n位整数相乘：需要进行n次移位和n次加法。我认为加法的时间复杂度是O(n)，因此相乘的时间复杂度为O(n^2)。 - Student

平方也类似，只是数字移位和移位模式相同。 - Student

Answer 6

我的想法是，要相乘两个n位整数，您的算法需要适用于任何两个n位整数。这是(2^n)^2种可能的输入。

一个平方算法只需要处理2^n种可能的输入，尽管它可以被建模为具有相同两个输入的乘法算法。

我猜想，在您知道两个输入将相同时，肯定有一些方法可以优化通用乘法算法，但我需要考虑一下。无论如何，那就是我要探究的领域...

- Andrew Cooper