On the Power of the Shift Instruction
Amir M. Ben-Amram, Zvi Galil · Information and Computation · 1995
This paper examines the power of the shift primitive when included in a high level model operatin 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 sam instruction set. The simulation is on-line, and its cost can be bounded by O(tα(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(α(s)) per operation).