Lookup Tables

Overview

When your processor runs at 1 MHz and lacks multiplication hardware, calculating sine values in real-time is impossible. Lookup tables solved this by pre-computing results and storing them in memory. Need sin(45°)? Look it up instantly. The technique traded RAM for speed—a bargain on systems where cycles were precious.

The problem

Operation	6502 cycles
Addition	2-4
Multiplication	100-200 (software)
Division	200-400 (software)
Sine/cosine	500+ (software)

Real-time games couldn’t afford these costs.

The solution

Pre-calculate and store:

sine_table:
    .byte 0, 3, 6, 9, 12, 15, 18, 21   ; sin(0°) to sin(7°) × 256
    .byte 24, 27, 30, 33, 36, 39, 42, 45
    ; ... continue for full circle

get_sine:
    ldx angle          ; angle as index
    lda sine_table,x   ; instant lookup
    rts                ; 6 cycles total

Common lookup tables

Table	Use
Sine/cosine	Rotation, movement
Multiplication	Scaling, coordinates
Square root	Distance calculation
Screen addresses	Fast plotting
Colour cycling	Animation effects

Multiplication tables

8×8 multiplication via lookup:

; Result = (a+b)² - (a-b)² / 4
; Pre-calculate squares, lookup both terms

square_table_lo:
    .byte <(0*0), <(1*1), <(2*2), ...
square_table_hi:
    .byte >(0*0), >(1*1), >(2*2), ...

Screen address tables

Fast pixel plotting:

screen_lo:
    .byte <$0400, <$0428, <$0450, ...  ; Each row start
screen_hi:
    .byte >$0400, >$0428, >$0450, ...

plot_pixel:
    ldy row
    lda screen_lo,y
    sta ptr
    lda screen_hi,y
    sta ptr+1
    ; Now ptr points to row start

Memory vs speed tradeoff

Table size	Lookup time	Calculation time
256 bytes	~6 cycles	100-500 cycles
1KB	~8 cycles	Same
Memory cost	Once	Every frame

Interpolation

When table resolution insufficient:

1. Look up nearest values
2. Interpolate between them
3. Still faster than calculation

Platform examples

C64

• Screen row addresses
• Colour cycling tables
• Sprite multiplexer Y-sorts

ZX Spectrum

• Screen address calculation (complex layout)
• Attribute addresses
• Trigonometry for 3D

NES

• PPU address mapping
• Collision tables
• Sine for movement

Limitations

Limitation	Mitigation
Memory cost	Reduce precision
Table generation	Pre-calculate at compile
Precision limits	Interpolate if needed

See also

• Fixed-Point Math
• 6502
• Z80
• Sprite Multiplexing