0
$\begingroup$

Found this in solutions of a test as being true

If you can square an n-bit integer in time $O(n \,log \,n)$, then you can multiply two n-bit integers in time $O(n \, log \,n)$.

How does the above scenario apply for multiplying different numbers? Isn't it possible that squaring is a special operation since it is just 1 number? . I would see this making sense.

If you can multiply two n-bit integers in time $O(n \, log \,n)$, then you can square an n-bit integer in time $O(n \,log \,n)$.

$\endgroup$
3
  • 1
    $\begingroup$ There is a simple method to calculate a*b as the sum of three squares. (a+b)^2=a^2+2ab+b^2. $\endgroup$ – gnasher729 Apr 17 at 15:58
  • $\begingroup$ cs.stackexchange.com/a/138381/755 $\endgroup$ – D.W. Apr 18 at 2:39
  • $\begingroup$ I think gnasher729 is easier to get as this is the equation that most people see in math. The post from D.W. isn't straight forward at first site and makes sense if you look at it after gnasher729's comment. $\endgroup$ – heretoinfinity Apr 20 at 18:26
1
$\begingroup$

Of course, we can suppose we are able to do sum and difference in linear time. Now, if we want to calculate $h\cdot k$, we can find in linear time $a$ and $b$ such that $h=a-b$ and $k=a+b$: take $a=\frac{k+h}{2}$ and $b=\frac{k-h}{2}$. Then $h\cdot k=(a-b)(a+b)=a^2-b^2$, so we only need to square two numbers of at most $n$ digits (if $h$ and $k$ have $n$ digits, then also $\frac{k+h}{2}$ has at most $n$ digits) in $O(n\log(n))$ and take their difference in $O(n)$.

Actually, this works if $h$ and $k$ have the same parity, else $a$ and $b$ are not integers; if it is not the case, then you can write $h\cdot k=h\cdot(k-1)+h$ and proceed as above.

$\endgroup$
1
  • $\begingroup$ You don’t need to distinguish parity: just use $ab=\frac14\bigl((a+b)^2-(a-b)^2\bigr)$. $\endgroup$ – Emil Jeřábek Apr 18 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.