LOWER BOUNDS FOR COMPUTATIONS WITH THE FLOOR OPERATION

被引：12

作者：

MANSOUR, Y ^{[1
]}

SCHIEBER, B ^{[1
]}

TIWARI, P ^{[1
]}

机构：

[1] IBM CORP, THOMAS J WATSON RES CTR, DIV RES, YORKTOWN HTS, NY 10598 USA

来源：

SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 02期

关键词：

ALGORITHMS; LOWER BOUND; SQUARE-ROOT; NEWTON ITERATION; MOD OPERATION; FLOOR OPERATION; TRUNCATION;

D O I：

10.1137/0220020

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A general lower bound technique is developed for computation trees with operations {+, -, *, /, [.], <} 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 [log x], etc. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with operations {+, -, *, /, [.], <} 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].

引用

页码：315 / 327

页数：13

共 30 条

[11] ON COMPUTATIONS WITH INTEGER DIVISION [J].

JUST, B ;

AUFDERHEIDE, FM ;

WIGDERSON, A .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1989, 23 (01) :101-111

[12]

Kung H. T., 1973, Journal of Computer and System Sciences, V7, P334, DOI 10.1016/S0022-0000(73)80027-3

[13] LOWER TIME-BOUNDS FOR INTEGER PROGRAMMING WITH 2 VARIABLES [J].

LAUTEMANN, C ;

HEIDE, FMAD .

INFORMATION PROCESSING LETTERS, 1985, 21 (02) :101-105

[14] THE COMPLEXITY OF APPROXIMATING THE SQUARE ROOT [J].

MANSOUR, Y ;

SCHIEBER, B ;

TIWARI, P .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :325-330

[15]

MANSOUR Y, 1989, LECT NOTES COMPUT SC, V372, P559

[16]

MANSOUR Y, 1988, RC14271 IBM TJ WATS

[17]

MANSOUR Y, 1988, 29TH P IEEE S F COMP, P51

[18]

MANSOUR Y, 1988, TR14272 IBM TJ WATS

[19]

PATERSON MS, 1972, P S COMPLEXITY COMPU, P41

[20]

PAUL W, 1981, MONOGRAPHIE ENSEIGME, V30, P331

← 1 2 3 →