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$ 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$ Apr 18 at 17:38

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .