A discussion is presented of parallel division algorithms that can be classified among modified higher radix nonrestoring online division methods, where redundant representations are extensively utilized to speed up t...
详细信息
A discussion is presented of parallel division algorithms that can be classified among modified higher radix nonrestoring online division methods, where redundant representations are extensively utilized to speed up the operation. The network realizations of these algorithms are cellular, or even systolic with exclusively local control; they have both size (area) and time of O(n), where n is the length of the dividend representation. The same structures can also be used as a signed, digit-serial multiplier. When suitably equipped with some control and a few registers, the divider/multiplier brings remarkable performance to large modular arithmetic, RSA cryptography, and greatest common divisor computations. They are also of interest for the design of floating-point units and signal processing applications
We deal with the following on-line 2-satisfiability problem P(m, n): starting from C(0)=true, consider a sequence of m Boolean formulas C(k) (in n variables and in conjunctive normal form), each of them being the inte...
详细信息
We present the Smart Next Fit algorithm for on-line bin packing, which is obtained by slightly modifying the Next Fit algorithm. For any list of items, this algorithm uses the smallest number of bins among all on-line...
详细信息
We present the Smart Next Fit algorithm for on-line bin packing, which is obtained by slightly modifying the Next Fit algorithm. For any list of items, this algorithm uses the smallest number of bins among all on-line algorithms that have only one active bin at any time. We analyze its average-case performance when the item sizes are uniformly distributed over (0, b), b less than or equal to 1. For b less than or equal to 1/2, the Smart Next Fit algorithm behaves exactly like the Next Fit algorithm. For 1/2 < b less than or equal to 1, its average-case performance is significantly better than that of Next Fit. For b = 1, its average-case performance rate is 1.2274113..., compared to 1.333... for Next Fit. Its average-case performance is better than that of any known constant-space algorithm.
We consider the problem of packing rectangles into bins which are unit squares. We give an on-line algorithm that uses at most 3.25 times the optimal number of bins. We also prove a result for the case when the items ...
详细信息
We consider the problem of packing rectangles into bins which are unit squares. We give an on-line algorithm that uses at most 3.25 times the optimal number of bins. We also prove a result for the case when the items to be packed are squares and discuss extensions to higher dimensions.
An algorithm to convert redundant number representations into conventional representations is presented. The algorithm is performed concurrently with the digit-by-digit generation of redundant forms by schemes such as...
详细信息
An algorithm to convert redundant number representations into conventional representations is presented. The algorithm is performed concurrently with the digit-by-digit generation of redundant forms by schemes such as SRT division. It has a step delay roughly equivalent to the delay of a carry-save adder and simple implementation. The conversion scheme is applicable in arithmetic algorithms such as nonrestoring division, square root, and on-line operations in which redundantly represented results are generated in a digit-by-digit manner, from most significant to least significant.
In this note we give lower bounds for such a one-dimensional bin-packing problem, in which we can use only one-line rules to pack the elements, and the maximal size of the elements are bounded. Our lower bound contain...
详细信息
In this note we give lower bounds for such a one-dimensional bin-packing problem, in which we can use only one-line rules to pack the elements, and the maximal size of the elements are bounded. Our lower bound contains, as a special case, the result given by Liang [Inform. Proc. Lett., 10 (1980), pp. 76–79].
作者：
SIPS, HJDepartment of Applied Physics
Delft University of Technology Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions
For the realization of a bit-sequential multiplier with operands of length n, Chen and Willoner1 suggest a circuitry consisting of 2n identical modules. It is shown that if a slightly different arrangement of the modu...
详细信息
For the realization of a bit-sequential multiplier with operands of length n, Chen and Willoner1 suggest a circuitry consisting of 2n identical modules. It is shown that if a slightly different arrangement of the modules is taken, the number of modules is reduced to n. Furthermore, the implementation in circuit form can be made more simple.
Focuses on the use of on-line algorithm for fitting straight lines between data ranges. Problems in finding straight lines between data ranges; Interpretations of data ranges; Computations of data using incremental pr...
详细信息
Focuses on the use of on-line algorithm for fitting straight lines between data ranges. Problems in finding straight lines between data ranges; Interpretations of data ranges; Computations of data using incremental process.
作者：
SAMET, HDepartment of Computer Science
University of Maryland Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions
An algorithm is presented for proving equivalence and inequivalence of instances of formulas involving constant terms. It is based on the construction of an equality data base in the form of a grammar. The algorithm d...
详细信息
An algorithm is presented for proving equivalence and inequivalence of instances of formulas involving constant terms. It is based on the construction of an equality data base in the form of a grammar. The algorithm differes from other approaches to the problem by being an on-line algorithm. Equality between two formulas can be proved in time proportional to the number of constant and function symbols appearing within them. An algorithm is also given for updating the equality data base. It has a worse case running time which is proportional to the square of the number of different formulas previously encountered.
暂无评论