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

CHAPTER SIX

SEARCHING

6.1. SEQUENTIAL SEARCHING

[397]

Program S (Sequential search). Assume that the keys K_i are stored as an array of octabyte values.

The following subroutine has three parameters: key ≡ LOC(K₁); n ≡ N, the number of keys; and k ≡ K, the key we want to find. After a successful search, the subroutine returns the location of the key found; otherwise, it returns zero. For efficiency, register i is scaled by 8, the size of the table entries. Further, we subtract 8N, the table size, from i and add it to key. With this trick, we can replace the test i ≤ N by 8(i − N) < 0 and control the loop with a single PBN instruction.

01	:Search	SL	i,n,3	1	S1. Initialize.
02	NEG	i,i	1	i ← –8N, i ← 1.
03	SUBU	key,key,i	1	key ← LOC(KN + 1).
04	S2