caa a22 4500 469033940 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF01272076 doi (NATIONALLICENCE)springer-10.1007/BF01272076 Fast exponentiation using the truncation operation [Elektronische Daten] [Nader Bshouty, Yishay Mansour, Baruch Schieber, Prasson Tiwari] Given an integerk, and anarbitrary integer greater than $$2^{2^k } $$ , we prove a tight bound of $$\Theta (\sqrt k )$$ on the time required to compute $$2^{2^k } $$ 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 $$O(\sqrt {\log n} )$$ time algorithm for computing ⌊log loga⌋, for alln-bit integersa. 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. Birkhäuser Verlag, 1992 68Q40 nationallicence Bshouty Nader Department of Computer Science, University of Calgary, T2N 1N4, Calgary, Canada aut Mansour Yishay IBM-Research Division, T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, NY aut Schieber Baruch IBM-Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY aut Tiwari Prasson Department of Computer Science, University of Wisconsin, 1210 W. Dayton St., 53706, Madison, WI aut computational complexity Birkhäuser-Verlag 2/3(1992-09-01), 244-255 1016-3328 2:3<244 1992 2 37 https://doi.org/10.1007/BF01272076 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01272076 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bshouty Nader Department of Computer Science, University of Calgary, T2N 1N4, Calgary, Canada aut NATIONALLICENCE 700 1- Mansour Yishay IBM-Research Division, T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, NY aut NATIONALLICENCE 700 1- Schieber Baruch IBM-Research Division, T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY aut NATIONALLICENCE 700 1- Tiwari Prasson Department of Computer Science, University of Wisconsin, 1210 W. Dayton St., 53706, Madison, WI aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/3(1992-09-01), 244-255 1016-3328 2:3<244 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer