Lower Bounds for Computations with the Floor Operation

DOI10.1137/0220020zbMath0724.68051OpenAlexW2071959614MaRDI QIDQ3212292

Yishay Mansour, Baruch Schieber, Prasoon Tiwari

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220020

zbMATH Keywords

algorithmstruncationNewton iterationlower boundssquare rootfloor operationmod operation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

Fast exponentiation using the truncation operation ⋮ A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks ⋮ A tight bound for approximating the square root ⋮ P-RAM vs. RP-RAM ⋮ Does indirect addressing matter? ⋮ Arbitrary sequence RAMs ⋮ Lower bounds on algebraic random access machines ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings