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$
  • $\begingroup$ Why do you think the page is talking about bit complexity? $\endgroup$ – Yuval Filmus Sep 9 '17 at 10:21
  • $\begingroup$ Because when speaking of words it takes $O(1)$ time. $\endgroup$ – rus9384 Sep 9 '17 at 11:05
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, privacy policy and cookie policy

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