Abstract:
We show that on a RAM with addition, subtraction, bitwise
Boolean operations and shifts, but no multiplication, there is a
trans-dichotomous solution to the static dictionary problem using linear
space and with query time 
. On the way,
we show that two w-bit words can be multiplied in time 
and that time 
is necessary, and that 
time is necessary and sufficient for identifying the least significant set
bit of a word
Available as PostScript, PDF, DVI.