@Article{Ben-AmramGalil:95,
  title =        "On the Power of the Shift Instruction",
  author =       "Amir M. Ben-Amram and Zvi Galil",
  pages =        "19--36",
  journal =      "Information and Computation",
  month =        "15~" # feb,
  year =         "1995",
  volume =       "117",
  number =       "1",
  abstract =     "This paper examines the power of the shift primitive
                 when included in a high level model operating on
                 unbounded integers. It is shown that in such a model a
                 constant number of registers suffices for simulating an
                 unbounded memory RAM of the same instruction set. The
                 simulation is on-line, and its cost can be bounded by
                 $O(t\alpha(s))$, for a RAM program of running time~$t$
                 and space~$s$. By multitask programming (postponing
                 lengthy updates) it can be made close to real-time
                 ($O(\alpha(s))$ per operation).",
}