为什么一个平方数相乘比两个随机数更快？ [英] Why is squaring a number faster than multiplying two random numbers?

问题描述

乘两个二进制数占据N ^ 2次，但一个平方数，可以更有效地完成某种方式。 （n为位数）如何可能？

或者是不可能的？这是疯狂！

解决方案

1. 目前存在的算法效率比O（N ^ 2）两个数相乘（见Karatsuba的，波拉德，Schönhage-Strassen的，等等。）

2. 这两个问题乘法两个任意N位数字和四方形的任意N位号码具有相同的复杂性。

我们有

  4 * X * Y =（X + Y）^ 2  - （X-Y）^ 2
 

因此​​，如果平方N位整数需要O（F（N））的时间，然后两个任意N位整数，该产品可在O（F（N））也获得。 （即2×N位总和，2个N位平方，1×2N位和，和1x 2N位移位）

和我们显然有

  X ^ 2 = X * X
 

因此​​，如果乘两个N位整数需要O（F（N）），那么一平方N位整数，可以为O完成（F（N））。

不限算法计算所述产品（RESP的平方）提供了一种算法来计算的平方（RESP）的产物与相同渐近成本

正如在其他的答案所指出的，用于快速乘法算法可以简化平方的情况下。增益将是在F（N）前的恒定，而不是F（N）本身。

Multiplying two binary numbers takes n^2 time, yet squaring a number can be done more efficiently somehow. (with n being the number of bits) How could that be?

Or is it not possible? This is insanity!

解决方案

1. There exist algorithms more efficient than O(N^2) to multiply two numbers (see Karatsuba, Pollard, Schönhage–Strassen, etc.)

2. The two problems "multiply two arbitrary N-bit numbers" and "Square an arbitrary N-bit number" have the same complexity.

We have

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

So if squaring N-bit integers takes O(f(N)) time, then the product of two arbitrary N-bit integers can be obtained in O(f(N)) too. (that is 2x N-bit sums, 2x N-bit squares, 1x 2N-bit sum, and 1x 2N-bit shift)

And obviously we have

x^2 = x * x

So if multiplying two N-bit integers takes O(f(N)), then squaring a N-bit integer can be done in O(f(N)).

Any algorithm computing the product (resp the square) provides an algorithm to compute the square (resp the product) with the same asymptotic cost.

As noted in other answers, the algorithms used for fast multiplication can be simplified in the case of squaring. The gain will be on the constant in front of the f(N), and not on f(N) itself.

这篇关于为什么一个平方数相乘比两个随机数更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！