A multilective circuit is one that reads its inputs more than once. Most functions can be computed by a multilective circuit more rapidly, and/or in less area, than by a “unilective” circuit (one that reads each input exactly once). But how much more rapidly? How much less area? What are the tradeoffs between speed and area for multilective circuits? Savage treats these questions from a theoretical perspective, proving theorems about asymptotic performance figures. His writing is admirably lucid, even though the mathematical nature of his subject makes for slow reading.

Most of Savage’s theorems are weak and will be improved someday. Nonetheless, his paper defines the current “state-of-the-art” of multilective circuit theory. His discussion and bibliography are comprehensive. As of August 1985, only one result can be added to Savage’s list: Siegel [1,2] has proved asymptotically tight bounds on the area of multilective circuits that sort n k-bit numbers.