Real-Ram Model Vs. Realistic Models Of Computation: The Computational Geometry Perspective

The Real-RAM Model: Idealized Yet Limited

The Real-RAM model, widely used in computational geometry algorithm analysis and design, assumes a hypothetical computing machine with infinite memory and constant-time arithmetic operations on nonnegative integers of arbitrary length. Defining properties include:

• Infinite memory capacity for storing integers of any size
• Basic arithmetic operations (+, -, *, %) on arbitrary-length integers take constant time regardless of operand size
• Other basic operations like comparisons, assignments, array access take constant time

The simplicity of the Real-RAM makes it amenable to elegant algorithm analysis and allows a focus on conceptual complexity rather than hardware details. Geometric algorithms leveraging paradigm like divide-and-conquer approach problems by recursively reducing them to smaller subproblems that can be independently solved in constant time.

However, the Real-RAM abstractions imply unrealistic assumptions about memory and arithmetic costs. Modern computers have large but finite random access memory and significant variable costs in accessing memory locations. Integer arithmetic logic circuits scale in time/space with operand bit lengths.

Limitations of the Real-RAM Model

The Real-RAM model ignores practical computation constraints in two major areas:

• Memory access costs – Each memory access takes constant time in the Real-RAM model regardless of data locality or access patterns. In reality, accessing RAM and caches incur variable latency.
• Unrealistic arithmetic unit costs – Integer operations have bit complexity linear in the operand size. Large integer multiplications can take thousands of times longer than simple additions.

Seeking Realistic Models

Various augmented machine models address the Real-RAM limitations by incorporating aspects of real computing systems like memory hierarchies and logical complexity of operations.

The Logarithmic-cost RAM

To better model the bit complexity of integer arithmetic, the logarithmic-cost RAM charges time proportional to the bit length for operations like multiplication and division. Adding two n-bit integers takes O(n) time compared to O(1) on the Real-RAM. More precisely:

• Addition, subtraction, comparison: O(n)
• Multiplication, division, remainder: O(n log n)

This impacts the analysis of geometric algorithms. Consider multiplying two d-digit integers using the grade school method:

long mult_logn(long x, long y):
   long sum = 0
   for i = 0 to d-1:
      if (y & (1 << i)) != 0:         // Check ith bit  
         sum += (x << i)               // Accumulate x << i
   return sum

The bitshifts and accumulation steps each take O(d) = O(log n) time, so overall bit complexity = O(d²) = O((log n)²) = O(log² n)

The External Memory (EM) Model

The EM model focuses on I/O complexity - the number of disk blocks transferred, assuming fast internal memory of size M and large external disk blocks each holding B consecutive words. This reflects the two-level storage hierarchy in most systems. Some results for geometric problems:

• Sorting N elements: Θ((N/B) log_M/B (N/M)) I/Os
• FFT on N point vector: Θ(N/B log_M/B N) I/Os

An optimal EM algorithm to report all intersecting pairs in a set of N line segments could work as follows:

1. Split plane into M/B vertical slabs, each containing ≤ M/B segments.
2. Find intersections within each slab using internal memory plane sweep.
3. For each slab, output resulting intersecting pairs.

This takes O((N/B) log_M/B N) I/Os, which is optimal in the EM model.

The Cache-Oblivious Model

The cache-oblivious model aims for optimal cache performance despite not knowing hardware specifics like cache size or replacement policy. The key technique is to carefully structure algorithms to exploit locality of memory references. For example, this cache-oblivious matrix transpose routine divides the matrix into quadtrees until submatrices fit in cache:

transpose(double A[N][N], int n):
  if n equals base case size:
    naive transpose of A
  else:
    evenly partition A into 4 n/2 x n/2 submatrices
    # Recursively transpose each submatrix 
    for i = 0 to 3:
      for j = 0 to 3:
        transpose(A[n/2*i][n/2*j], n/2)

    # Transpose submatrix order  
    for i = 0 to 3:
      for j = 0 to 3:
        if i != j:
          swap A[n/2*i][n/2*j] and A[n/2*j][n/2*i]

This quadtree block swapping pattern ensures optimal reuse of recursively transposed submatrices. The algorithm matches optimal Θ(N²/B + N/L) cache complexity bounds without needing to know B or L.

No Perfect Model Exists

Each model above explores specific aspects of real-world computation - arithmetic costs, memory hierarchies, caching effects. Simplifying assumptions are always necessary to enable useful analysis. Key tradeoffs exist:

• Realism vs simplicity - More detailed models can become impractical for algorithmic analysis. The Real-RAM's simplicity enables elegant algorithm development.
• Generality vs specialization - Models tailored to cache behavior may not translate to new hardware paradigms like 3D memory stacking.
• Accuracy vs tractability - Precise modeling of instruction pipelines may not yield closed-form solutions.

Thus no model perfectly captures reality while remaining analytically tractable. Algorithm designers must choose an appropriate abstraction level based on context such as hardware expectations, problem dimensions, and performance objectives.

The Real-RAM retains usefulness as an intuitive, worst-case indicator of algorithmic complexity despite hardware advances. Augmented models help relate this conceptual foundation to empirical performance on modern platforms. Ongoing improvements to both models and algorithms will enable solving larger problems in less time.