Space-Time Tradeoffs for Oblivious Interger Multiplications
Space-Time Tradeoffs for Oblivious Interger Multiplications
复制标题
不经意的整数乘法的时空权衡
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
S. Swamy
中科院分区：
文献类型：
--
作者：
J. Savage;S. Swamy
Grigoryev的结果的延伸是用来推导整数乘法时，实现直线算法所需的时空积的下界。如果S是随机存取机上直线算法所用的暂存单元数，T是计算步数，则当直线算法的基础是布尔函数集时，证明了二进制整数乘法的（S+1）T <$Ω（n2）.
An extension of a result by Grigoryev is used to derive a lower bound on the space-time product required for integer multiplication when realized by straight-line algorithms. If S is the number of temporary storage locations used by a straight-line algorithm on a random-access machine and T is the number of computation steps, then we show that (S+1)T ⩾ Ω(n2) for binary integer multiplication when the basis for the straight-line algorithm is a set of Boolean functions.