# Convention for RAM machine models

When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used?

My understanding is that most problems use unit-cost RAM, but some (such as integer multiplication) use log-cost RAM, and for some others it depends on the author.

Unit-cost appears simpler to map to commonly used algorithms (hence its popularity), while log-cost RAM appears more accurate as a true measure of compute.

For log-cost RAM, it appears there is a standard up to linear time equivalence.

For unit-cost RAM, there are different possibilities (in order of decreasing model power):
a. (naive) unlimited word size with multiplication
b. unlimited word size (with addition but not multiplication)
c. log-limited word size (with different conventions)
d. pointer machines (also called storage modification machines; this is a natural model but appears more restrictive than unit-cost RAM).

I think the convention is (c), but even here we have different choices. A sensible choice for $\mathrm{TimeSpace}(t, s \, \mathrm{cells})$ with $s≤t$ is to have cells $0..O(s)$ each storing a number $0..(s+\mathrm{inputlength})^{O(1)}$, with $\mathrm{Time}(O(t)) = \mathrm{TimeSpace}(O(t), O(t) \, \mathrm{cells})$ (assuming $t$ is above the input length; I am not sure if using $t^{O(1)}$ cells gives an equivalent model). However, I do not know whether this is the standard, whether there are other subtleties, or if the unit-cost RAM is undefined for algorithms using more than polynomial space.

• Actually if you take a paper on integer multiplication, like the best known algorithm at the moment [1], they explicitely mention that they work with multitape Turing machines. This means one has to be careful when manipulating arrays. [1] Even faster integer multiplication, David Harvey and Joris van der Hoeven and Grégoire Lecerf – Amaury Pouly Dec 10 '17 at 14:15
• Also my experience is that if the paper uses a Turing machine model (or more or less equivalenty a log-cost RAM) then they mention "bit complexity" whereas if they use unit-cost RAM they mention "arithmetic complexity". Depending on the field, what is the default varies: in algebraic geometry and formal methods, unit-cost is more common but everywhere else bit-complexity is standard I think. – Amaury Pouly Dec 10 '17 at 14:27
• Not too relevant, but the question is not 2+ years old. Also, I'm not sure that there's a convention. – domotorp May 24 at 7:19
• What are examples of time/space complexity given without specifying the model? In my experience, such works rather say “this algorithm performs so much relevant-type operations”, ignoring everything else. – Dmitri Urbanowicz May 24 at 17:36