Lower Bounds for Computations with the Floor Operation
| Autor: | Yishay Mansour, Prasoon Tiwari, Baruch Schieber |
|---|---|
| Rok vydání: | 1991 |
| Předmět: |
Discrete mathematics
Mathematics::Combinatorics Modulo operation General Computer Science General Mathematics Computation Computer Science::Computational Geometry Upper and lower bounds symbols.namesake Square root Computer Science::Discrete Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY symbols Calculus Parity (mathematics) Newton's method Time complexity Square number MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | SIAM Journal on Computing. 20:315-327 |
| ISSN: | 1095-7111 0097-5397 |
| Popis: | A general lower bound technique is developed for computation trees with operations $\{ + , - , * ,/,\lfloor \cdot \rfloor , < \} $ and constants $\{ 0,1\} $, for functions that have as their input a single n-bit integer. The technique applies to many natural functions, such as perfect square root (deciding if the square root of the input is integral or not), computing the parity of $\lfloor {\log x} \rfloor $ , etc. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with operations $\{ + , - , * ,/,\lfloor \cdot \rfloor , < \} $ that solves the problem. Another related result is described in a companion paper [Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988] and [J. Assoc. Comput. Mach., 1991, to appear]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|