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 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

[Anonymous], 1988, GEOMETRIC ALGORITHMS, DOI DOI 10.1007/978-3-642-97881-4

[3] ON THE LIMITS OF COMPUTATIONS WITH THE FLOOR FUNCTION [J].

BABAI, L ;

JUST, B ;

HEIDE, FMAD .

INFORMATION AND COMPUTATION, 1988, 78 (02) :99-107

[4]

Cassels J. W. S., 1971, INTRO GEOMETRY NUMBE

[5]

COBHAM A, 1966, RC1704 IBM TJ WATS R

[6]

DERHEIDE FMA, 1989, LECTURE NOTES COMPUT, V349, P1

[7] LOWER BOUNDS FOR SORTING WITH REALISTIC INSTRUCTION SETS [J].

DITTERT, E ;

ODONNELL, MJ .

IEEE TRANSACTIONS ON COMPUTERS, 1985, 34 (04) :311-317

[8]

DITTERT E, 1986, IEEE T COMPUT, V35, P932, DOI 10.1109/TC.1986.1676690

[9]

HOUSEHOLDER A. S., 1970, NUMERICAL TREATMENT

[10] ON THE CONTROL POWER OF INTEGER DIVISION [J].

IBARRA, OH ;

MORAN, S ;

ROSIER, LE .

THEORETICAL COMPUTER SCIENCE, 1983, 24 (01) :35-52

← 1 2 3 →