patternMinor
Linear time multiplication on RAM machine?
Viewed 0 times
linearmultiplicationtimemachineram
Problem
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?
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?
Solution
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
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
Context
StackExchange Computer Science Q#81042, answer score: 2
Revisions (0)
No revisions yet.