Sökning: onr:"swepub:oai:DiVA.org:ltu-27065" >
Trans-dichotomous a...
Trans-dichotomous algorithms without multiplication : some upper and lower bounds
-
- Brodnik, Andrej (författare)
- Luleå tekniska universitet,Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
-
- Miltersen, Peter Bro (författare)
- BRICS, Centre of the Danish National Research Foundation University of Aarhus, Denmark
-
- Munro, J. Ian (författare)
- Department of Computer Science, University of Waterloo, Ontario, Canada
-
(creator_code:org_t)
- 2005-07-30
- 1997
- Engelska.
-
Ingår i: Algorithms and Data Structures. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 9783540633075 ; , s. 426-439
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear space and with query time log n(log log n)1+0(1). On the way, we show that two w-bit words can be multiplied in time (log w)1+0(1) and that time (log w) is necessary, and that (log log w) time is necessary and sufficient for identifying the least significant set bit of a word.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Dependable Communication and Computation Systems
- Kommunikations- och beräkningssystem
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas