为什么比乘以两个随机数更快地对数字进行平方？

Question

将两个二进制数相乘需要n ^ 2次,但是以某种方式可以更有效地对数字进行平方.(n是位数)这怎么可能？

还是不可能？这是精神错乱!

Answer 1

1. 存在比O(N ^ 2)更有效的算法来乘以两个数字(参见Karatsuba,Pollard,Schönhage-Strassen等).

2. 两个问题"乘以两个任意N位数"和"平方任意N位数"具有相同的复杂性.

我们有

4*x*y = (x+y)^2 - (x-y)^2

因此,如果对N位整数求平均需要O(f(N))时间,那么也可以在O(f(N))中获得两个任意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)本身上.

Answer 2

平方n位数可能比乘以两个随机n位数更快.谷歌搜索我发现了这篇文章.它是关于任意精度算术,但它可能与你的要求有关.作者在其中说:

在对大整数求平方,即X ^ 2 =(xn-1,xn-2,...,x1,x0)^ 2时,形式xi*xj和xj*xi的许多叉积项是等价的.它们只需要计算一次然后左移以便加倍.仅使用(n ^ 2 + n)/ 2个单精度乘法执行n位平方运算.

Answer 3

正如其他人所指出的那样,平方只能比任意数字之间的常规乘法快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 * ui对i=0, 1, ..., 4形成对角,而忽略他们,你会看到这些元素ui * uj的i ? j重复两次.

因此,您需要做的就是计算对角线以下元素的乘积和,并将其加倍,左移.你最后添加了对角线元素.现在您可以看到2X加速的来源.实际上,由于对角线和额外操作,加速度约为1.5倍.

Answer 4

我相信你可能指的是通过平方来取幂.该技术不用于乘法,而是用于提高功率x ^ n,其中n可能很大.不是将x倍乘以N倍,而是执行一系列平方和添加操作,这些操作可以映射到N的二进制表示.乘法运算的数量(比大数的加法更昂贵)从N减少到关于朴素求幂算法的log(N).

Answer 5

假设您想展开乘法(a+b)\xc3\x97(c+d)。它分为四个单独的乘法：a\xc3\x97c + a\xc3\x97d + b\xc3\x97c + b\xc3\x97d.

\n\n

但如果你想展开(a+b)\xc2\xb2，那么它只需要三次乘法（和一次加倍）：a\xc2\xb2 + 2ab + b\xc2\xb2。

\n\n

（另请注意，其中两个乘法本身就是平方。）

\n\n

希望这只是开始让我们深入了解在常规乘法上执行平方时可能实现的一些加速。

\n