Research and Advances

Variable-width tables with binary-search facility

Posted

The family of subroutines described in this report was designed to create, search and maintain tables which are to contain entries of different lengths, and yet be amenable to search by partition, or “binary” search. It is designed explicitly for fixed-word-length binary machines; the tables in question are the argument-function type, with the two parts physically separated—i.e., no one machine word contains both, or parts of both. The family consists at present of seven subroutines, of which four are primitive and three second-generation. (By “primitive” is meant a self-sufficient routine; a second-generation routine is one which calls on one or more primitives.) These routines are at present coded for the IBM 709; with a few trivial changes they are ready also for the 704. The primitives are: (1) STT (Start Table), (2) TLU (Table Look-Up), (3) ITC (Increase Table Capacity), and (4) AOD (Append Ordered Data). The second-generation routines are: (1) INT (Insert in Table), (2) INX (Insert and Expand), and (3) ANX (Append and Expand). It is intended that this family be written, with modifications as necessary, for several stored-program computers. The calling-sequences for any one of the routines will, as far as possible, be identical on the several machines.

View this article in the ACM Digital Library.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More