O'Reilly logo

The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth by Martin Ruckert

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

PROGRAMMING TECHNIQUES

1. INDEX VARIABLES

Many algorithms traverse information structures that are sequentially allocated in memory. Let us assume that a sequence of n data items a0, a1, . . . , an−1 is stored sequentially. Further assume that each data item occupies 8 bytes, and the first element a0 is stored at address A; the address of ai is then A + 8i. To load ai with 0 ≤ i < n from memory into register ai, we need a suitable base address and so we assume that we have A = LOC(a0) in register a. Then we can write ‘8ADDU t,i,a; LDO ai,t,0’ or alternatively ‘SL t,i,3; LDO ai,a,t’. If this operation is necessary for all i, it is more efficient to maintain a register i containing 8i as follows:

SETi,0i 0.
LDOai,a,iLoad ai.
ADDi,i,8 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required