Prove or disprove: it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers

Question

Prove or disprove: it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers.

That seems like more of a theory question, for https://cs.stackexchange.com . Anyway consider the quarter square multiplication algorithm. — harold, Sep 09 '19 at 12:53
see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) where I compare exactly the same thing ... mul vs. sqr where sqr wins not just for naive `O(n^2)` versions but also for Schönhage-Strassen multiplication which has far more sense if you want n to go really high to make asymptotic notations relevant. However complexity stays the same ... its just much faster due to lower constant time as you do not need to compute half of therms in naive or one NTT in advanced version... — Spektre, Sep 10 '19 at 06:43

score 3 · Accepted Answer · answered Sep 09 '19 at 13:57

3

If x and y are two n bit numbers, then x+y is an n+1 bit number. ((x+y)^2 - x^2 - y^2)/2 is xy.

So multiplication of two n bit numbers is at most as expensive as 1 addition, three squarings, two subtractions, and a divide by 2.

Since addition, subtraction and division by 2 are Theta(n), this shows that squaring can't be asymptotically faster.

answered Sep 09 '19 at 13:57

Paul Hankin

yep they have the same complexities but sqr is faster due to smaller constant time so the sqr is faster `~2x` or `1/3x` depending on the multiplication algo used... – Spektre Sep 10 '19 at 06:57

1 Answers1