Since 2014
Trans-Dichotomous Algorithms without Multiplication —some Upper and Lower Bounds
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Trans-Dichotomous Algorithms without Multiplication —some Upper and Lower Bounds
|
|
| Creator |
Brodnik, Andrej
Miltersen, Peter Bro Munro, J. Ian |
|
| Description |
We show that on a RAM with addition, subtraction, bitwiseBoolean operations and shifts, but no multiplication, there is atrans-dichotomous solution to the static dictionary problem usinglinear space and with query time sqrt(log n(log log n)^(1+o(1))). Onthe way, we show that two w-bit words can be multiplied intime (log w)^(1+o(1)) and that time Omega(log w) is necessary, and thatTheta(log log w) time is necessary and sufficient for identifying theleast significant set bit of a word.
|
|
| Publisher |
Aarhus University
|
|
| Date |
1997-01-12
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/18803
10.7146/brics.v4i12.18803 |
|
| Source |
BRICS Report Series; No 12 (1997): RS-12 Trans-Dichotomous Algorithms without Multiplication —some Upper and Lower Bounds
BRICS Report Series; Nr. 12 (1997): RS-12 Trans-Dichotomous Algorithms without Multiplication —some Upper and Lower Bounds 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/18803/16448
|
|