Trans-Dichotomous Algorithms without Multiplication —some Upper and Lower Bounds - Brodnik, Andrej; Miltersen, Peter Bro; Munro, J. Ian (BRICS Report Series, 1997)
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 sqrt(log n(log log n)^(1+o(1))). On the way, we show that two w-bit words can be multiplied in time (log w)^(1+o(1)) and that time Omega(log w) is necessary, and that Theta(log log w) time is necessary and sufficient for identifying the least significant set bit of a word.