WFRF:(Miltersen Peter Bro)
Search: WFRF:(Miltersen Peter Bro) > Trans-dichotomous a...
- 2 of 3
- Previous record
- Next record
- To hitlist
Trans-dichotomous algorithms without multiplication : some upper and lower bounds
-
- Brodnik, Andrej (author)
- Luleå tekniska universitet,Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
-
- Miltersen, Peter Bro (author)
- BRICS, Centre of the Danish National Research Foundation University of Aarhus, Denmark
-
- Munro, J. Ian (author)
- Department of Computer Science, University of Waterloo, Ontario, Canada
- (creator_code:org_t)
- 2005-07-30
- 1997
- English.
- In: Algorithms and Data Structures. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 9783540633075 ; , s. 426-439
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Dependable Communication and Computation Systems
- Kommunikations- och beräkningssystem
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
- Algorithms and Data Structures (Search for host publication in LIBRIS)
To the university's database
- 2 of 3
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Brodnik, Andrej
- Miltersen, Peter ...
- Munro, J. Ian
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Algorithms and D ...
- By the university
- Luleå University of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
