Paper Info
Title
On pointers versus addresses
Abstract
What is the cost of random access to memory? This fundamental problem M addressed by studying the simulation of random addressing by a machine that lacks it, a "pointer machine.'" The problem is formulated in the context of high-level computational models, allowing the use of a data type of our choice, A RAM program of time tand space s can be simulated m 0( f log .s) time using a tree. To enable a lower-bound proof, we formalize a notion of incompressibility for general data types. The main theorem states that for all incompressible data types an Ll( f log s) lower bound holds. Incompressibility trivially holds for strings, but is harder to prove for a powerful data type. Incompressibility is proved for the real numbers with a set of primitives that includes all functions that are continuous except on a countable closed set. This may be the richest set of operations considered m a lower-bound proof. It is also shown that the integers with arithmetic +, - , x and ( .x/2~ , any Boolean operations, and left shift are incompressible. Tbe situation is reversed once right shift is allowed.
Year
DOI
Venue
1992
10.1145/146637.146666
SFCS '88 Proceedings of the 29th Annual Symposium on Foundations of Computer Science
Keywords
Field
DocType
incompressibility,random access memory,pointer structures,pointers,time measurement,data type,space,computational complexity,tree,lower bound,real numbers,pointer machine,computational modeling,continuously differentiable,graph theory,arithmetic,functions,data structures,algorithm design and analysis,upper bound
Discrete mathematics,Pointer (computer programming),Data structure,Combinatorics,Pointer machine,Countable set,Kolmogorov complexity,Computer science,Upper and lower bounds,Closed set,Data type
Journal
Volume
Issue
ISSN
39
3
0004-5411
ISBN
Citations 
PageRank 
0-8186-0877-3
19
1.44
References 
Authors
22
2
Name
Order
Citations
PageRank
Amir M Ben-Amram132730.52
Zvi Galil236341426.98