请证明或证伪：平方n位整数的渐近速度是否快于两个n位整数相乘

Great question! Let's break this down step by step to figure out whether squaring an n-digit integer is asymptotically faster than multiplying two arbitrary n-digit integers.

In terms of asymptotic complexity, squaring an n-digit integer is NOT faster than multiplying two arbitrary n-digit integers—they have equivalent asymptotic running times.

First, let's use a mathematical trick that connects multiplication to squaring. For any two n-digit integers a and b, their product can be rewritten using squares:

ab = [(a + b)² - (a - b)²] / 4

Here's what this means for complexity:

• If we had an algorithm that could compute a square in O(f(n)) time, we could use it to compute any product in O(f(n)) time too. The operations (addition, subtraction, dividing by 4) all take linear O(n) time, which is dominated by f(n) if f(n) is superlinear (like the O(n log n) of fast multiplication algorithms).
• On the flip side, squaring is just a special case of multiplication (multiplying a number by itself), so the time to square can't be slower than the time to multiply two arbitrary numbers.

Put these two together, and we get that the asymptotic complexity of squaring is exactly the same as that of general multiplication.

Let's verify this with common multiplication methods:

• Traditional Long Multiplication: Both squaring and general multiplication run in O(n²) time. Squaring does let you skip some redundant calculations (e.g., a_i * a_j is the same as a_j * a_i, so you can compute once and double it), but this only reduces the constant factor—not the asymptotic growth rate. It's still O(n²).
• Fast Multiplication (FFT-Based): Advanced algorithms like the Fast Fourier Transform (FFT) bring multiplication down to O(n log n) (or O(n log n log log n) for more optimized variants). Squaring using FFT follows exactly the same steps: convert the number to the frequency domain, multiply each element by itself, then convert back. The number of operations is identical to multiplying two different numbers, so the asymptotic complexity stays the same.

While asymptotic complexity is identical, you might notice squaring runs a bit faster in practice. That's because we can optimize the constant factors:

• As mentioned earlier, squaring avoids redundant cross terms, so we have fewer additions to perform.
• Some low-level optimizations (like using precomputed values or specialized hardware instructions) can make squaring quicker for specific cases.

But remember: asymptotic analysis ignores constant factors. When we talk about "asymptotic speed," we're looking at how the running time grows as n gets extremely large. For that, squaring and general multiplication are tied.

内容的提问来源于stack exchange，提问作者Osama Arshad