Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
复制标题
Cell-Probe 模型中在线整数乘法和卷积的下界
DOI：
10.1007/978-3-642-22006-7_50
复制
发表时间：
2011
影响因子：
--
通讯作者：
Markus Jalsenius
中科院分区：
文献类型：
--
作者：
R. Clifford;Markus Jalsenius
我们给出了在字长为\(w\)的单元探测模型中在线整数乘法和卷积的时间下界。对于乘法问题，在第\(i\)步，作为输入给出一对数字，每个数字分别来自两个要相乘的\(n\)位数字中的一个。在线算法在第\(i + 1\)步之前输出乘积中的一个新数字。对于这个问题，我们给出每个输出数字平均时间的下界为\(\Omega(\delta / w\log n)\)，其中\(2\delta\)是一个数字的最大值。在卷积问题中，我们给定一个长度为\(n\)的固定向量\(V\)，并且考虑一个数字逐个到达的流。我们输出\(V\)与由流中最后\(n\)个数字组成的向量的内积。我们给出了流中每个新数字所需时间的\(\Omega(\delta / w\log n)\)下界。所给出的所有下界在随机化和分摊的情况下都成立。乘法和卷积是算法研究中的核心问题，它们也具有最广泛的实际应用。
We show time lower bounds for both online integer multiplication and convolution in the cell-probe model with word size w. For the multiplication problem, one pair of digits, each from one of two n digit numbers that are to be multiplied, is given as input at step i. The online algorithm outputs a single new digit from the product of the numbers before step i + 1. We give a lower bound of Ω(δ/w log n) time on average per output digit for this problem where 2δ is the maximum value of a digit. In the convolution problem, we are given a fixed vector V of length n and we consider a stream in which numbers arrive one at a time. We output the inner product of V and the vector that consists of the last n numbers of the stream. We show an Ω(δ/w log n) lower bound for the time required per new number in the stream. All the bounds presented hold under randomisation and amortisation. Multiplication and convolution are central problems in the study of algorithms which also have the widest range of practical applications.