将两个二进制数相乘需要 n^2 时间，但以某种方式可以更有效地完成一个数字的平方。（n 是位数）怎么可能？
还是不可能？这是精神错乱！
问问题
26146 次
14 回答
70
存在比 O(N^2) 更有效的算法来将两个数字相乘（参见 Karatsuba、Pollard、Schönhage–Strassen 等）
“两个任意 N 位数相乘”和“任意 N 位数平方”这两个问题具有相同的复杂性。
我们有
4*x*y = (x+y)^2 - (x-y)^2
因此，如果对 N 位整数求平方需要 O(f(N)) 时间，那么两个任意 N 位整数的乘积也可以在 O(f(N)) 中获得。（即 2x N 位和、2x N 位平方、1x 2N 位和和 1x 2N 位移位）
显然我们有
x^2 = x * x
因此，如果将两个 N 位整数相乘需要 O(f(N))，则可以在 O(f(N)) 中完成 N 位整数的平方。
任何计算乘积（对应于平方）的算法都提供了一种算法来计算平方（对应于乘积），具有相同的渐近成本。
如其他答案中所述，在平方的情况下，可以简化用于快速乘法的算法。增益将在 f(N) 前面的常数上，而不是在 f(N) 本身上。
于 2009-09-04T09:49:27.410 回答
15
对一个 n 位数字进行平方可能比将两个随机 n 位数字相乘更快。谷歌搜索我找到了这篇文章。它是关于任意精度的算术，但它可能与您的要求有关。作者在其中说：
在对一个大整数求平方时，即 X^2 = (xn-1, xn-2, ... , x1, x0)^2 许多 xi * xj 和 xj * xi 形式的叉积项是等价的。它们只需要计算一次，然后左移以加倍。仅使用 (n^2 + n)/2 单精度乘法执行 n 位平方运算。
于 2009-09-04T07:41:39.667 回答
7
就像其他人指出的那样，平方只能比任意数字之间的常规乘法快 1.5 倍或 2 倍。计算优势从何而来？是对称的。让我们计算平方1011并尝试找出我们可以利用的模式。u0:u3表示数字中从最高有效到最低有效的位。
1011 // u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3
1011 // u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3
0000 // u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3
1011 // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3
如果您考虑形成对角线的元素并忽略它们，您会看到元素ui * uifor重复了两次。i=0, 1, ..., 4ui * uji ≠ j
因此，您需要做的就是计算对角线以下元素的乘积和并将其加倍，并左移。您最终会添加对角线元素。现在您可以看到 2X 加速的来源。在实践中，由于对角线和额外的操作，加速大约是 1.5 倍。
于 2013-05-05T20:01:50.800 回答
6
我相信您可能指的是通过平方取幂。这种技术不用于乘法，而是用于提高到 x^n 的幂，其中 n 可能很大。不是将 x 乘以自身 N 次，而是执行一系列平方和加法运算，这些运算可以映射到 N 的二进制表示。乘法运算（比大数的加法更昂贵）的数量从 N 减少到log(N) 相对于朴素求幂算法。
于 2009-09-04T06:23:24.113 回答
4
你的意思是用一个数字乘以2的幂？这通常比任何两个随机数相乘要快，因为结果可以通过简单的位移来计算。但是，请记住，现代微处理器将大量的蛮力硅用于这些类型的计算，并且与旧微处理器相比，大多数算法的执行速度都非常惊人
于 2009-09-04T06:03:03.173 回答
3
我有！
2 * 2
比贵
2 << 1
（需要注意的是它只适用于一种情况。）
于 2009-09-04T06:26:33.857 回答
3
假设您想展开乘法(a+b)×(c+d)。它分为四个单独的乘法：a×c + a×d + b×c + b×d.
但是如果你想扩展出来(a+b)²，那么它只需要三个乘法（和一个加倍）：a² + 2ab + b².
（还要注意，其中两个乘法本身就是平方。）
希望这只是开始深入了解在常规乘法上执行平方时可能实现的一些加速。
于 2016-05-20T11:11:57.373 回答
1
首先是好问题！我希望有更多这样的问题。
所以事实证明，我想出的方法是 O(n log n) 仅用于算术复杂度的一般乘法。您可以将任何数字 X 表示为
X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0
在哪里
x_i, y_i \in {0,1}
然后
XY = sum _ {k=0} ^ m+n r_k 2^k
在哪里
r_k = sum _ {i=0} ^ k x_i y_{k-i}
这只是 FFT 的直接应用，可在 (n +m) log(n + m) 时间内找到每个 k 的 r_k 值。
然后对于每个 r_k 你必须确定溢出有多大并相应地加起来。对于一个数字的平方，这意味着 O(n log n)算术运算。
您可以使用 Schönhage–Strassen 算法更有效地将 r_k 值相加，以获得 O(n log n log log n) 位操作界限。
您的问题的确切答案已由 Eric Bainville 发布。
但是，您可以获得比 O(n^2) 更好的界限来对数字进行平方，因为存在更好的整数相乘界限！
于 2009-09-04T17:45:23.227 回答
0
如果您假设机器的字长固定长度并且要平方的数字在内存中，则平方操作只需要从内存中加载一次，因此可能会更快。
对于任意长度的整数，乘法通常是 O(N²)，但有一些算法可以减少大整数的乘法。
如果您假设使用简单的 O(N²) 方法将a乘以b ，那么对于a中的每个位，您必须移动b并将其添加到累加器（如果该位为 1）。对于 a 中的每一位，您需要 3N 次移位和加法。
注意
( x - y )² = x² - 2 xy + y²
因此
x² = ( x - y )² + 2 xy - y²
如果每个y是不大于 x 的 2 的最大幂，则这会减少到较低的平方、两次移位和两次加法。随着N在每次迭代中减少，您可能会获得效率增益（对称性意味着它访问三角形而不是矩形中的每个点），但它仍然是 O(N²)。
可能还有另一种更好的对称性可以利用。
于 2009-09-04T09:09:06.463 回答
0
a^2 (a+b)*(a+b)+b^2 例如。66^2 = (66+6)(66-6)+6^2 = 72*60+36= 4356
对于 a^n 只需使用幂规则
66^4 = 4356^2
于 2013-11-13T20:24:10.683 回答
0
我想通过一个数字的 N 位乘法来解决这个问题
A 位为 A(n-1)A(n-2)........A(1)A(0)。
B 位为 B(n-1)B(n-2)........B(1)B(0)。
对于数字 A 的平方，生成的唯一乘法位将是 A(0)->A(0)....A(n-1) A(1)->A(1)....A( n-1) 依此类推，因此总操作将是
OP = n + n-1 + n-2 ....... + 1 因此 OP = n^2+n/2; 所以渐近符号将是 O(n^2)
对于 A 和 B 的乘法，将生成 n^2 个唯一乘法，因此渐近符号将为 O(n^2)
于 2019-01-14T07:11:56.077 回答
-1
2 n的平方根是 2 n / 2或 2 n >> 1，因此，如果您的数字是 2 的幂，那么一旦您知道幂，一切都非常简单。相乘更简单： 2 4 * 2 8是 2 4+8。你所做的这些陈述毫无意义。
于 2009-09-04T06:08:46.170 回答
-1
如果你有一个二进制数 A，它可以（总是，留给急切的读者证明）表示为 (2^n + B)，这可以平方为 2^2n + 2^(n+1)B + B ^2。然后我们可以重复展开，直到 B 等于 0。我没有仔细研究它，但直觉上，感觉好像你应该能够使平方函数比通用乘法花费更少的算法步骤。
于 2009-09-04T08:02:26.490 回答
-4
我认为您的陈述完全错误
两个二进制数相乘需要 n^2 次
两个 32 位数字相乘需要一个时钟周期。在 64 位处理器上，我假设将两个 64 位数字相乘需要 1 个时钟周期。一个 32 位处理器可以在 1 个时钟周期内将两个 64 位数字相乘，这并不让我感到惊讶。
yet squaring a number can be done more efficiently somehow.
对数字求平方只是将数字与自身相乘，所以这只是一个简单的乘法。CPU 中没有“平方”运算。
也许您将“平方”与“乘以 2 的幂”混淆了。乘以 2 可以通过将所有位向“左”移动一位来实现。乘以 4 将所有位向“左”移动两个位置。8、3个位置。但是这个技巧只适用于二的幂。
于 2009-09-04T06:35:25.963 回答