3
$\begingroup$

This page says following:

Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM

Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) using RAM?

$\endgroup$
2
  • $\begingroup$ Why do you think the page is talking about bit complexity? $\endgroup$ Sep 9, 2017 at 10:21
  • $\begingroup$ Because when speaking of words it takes $O(1)$ time. $\endgroup$
    – rus9384
    Sep 9, 2017 at 11:05

1 Answer 1

2
$\begingroup$

The page is not fooling you. I'll refer you to the original paper, but accordingly they show the following:

Theorem 6.1 There exists an SMM which performs integer-multiplication in linear time, i.e. there is a constant $c$ such that any $2N$-bit input is read as the concatenation of two $N$-bit integers $x$, $y$, and after at most $cN$ many steps their product $z=xy$ is output in binary representation.

It is a rather detailed paper which would be silly to write up all here. See below.

Schönhage, A. (1980). Storage Modification Machines. SIAM Journal on Computing, 9(3), 490-508. https://doi.org/10.1137/0209036

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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