Dmitriy Katz-Rogozhnikov, Baruch Schieber, et al.
SPAA 2016
Given an integer k, and an arbitrary integer greater than {Mathematical expression}, we prove a tight bound of {Mathematical expression} on the time required to compute {Mathematical expression} with operations {+, -, *, /, ⌊·⌋, ≤}, and constants {0, 1}. In contrast, when the floor operation is not available this computation requires Ω(k) time. Using the upper bound, we give an {Mathematical expression} time algorithm for computing ⌊log log a⌋, for all n-bit integers a. This upper bound matches the lower bound for computing this function given by Mansour, Schieber, and Tiwari. To the best of our knowledge these are the first non-constant tight bounds for computations involving the floor operation. © 1992 Birkhäuser Verlag.
Dmitriy Katz-Rogozhnikov, Baruch Schieber, et al.
SPAA 2016
Avrim Blum, Prabhakar Raghavan, et al.
SIAM Journal on Computing
Guy Even, Joseph Naor, et al.
SIAM Journal on Computing
Allan Borodin, Prabhakar Raghavan, et al.
Journal of the ACM