The Complexity of a Pipelined Algorithm for Remainder Computing in a Given Modulo

摘要

A pipelined algorithm for computing the remainder when dividing an arbitrary binary number of a given bit capacity (numerator) by a certain constant value (a constant) is proposed. The algorithm is based on the same types of operations of comparisons and addition–subtraction of partial remainders upon division by this constant. Depending on whether an intermediate result during computation of the remainder is positive or negative, addition with the value of the intermediate result or subtraction from it of the remainder upon division of a given power of two occur. The number of algorithm stages compared with the model is known in advance and depends on the bit capacities of both the dividend and constants. The estimates of the time complexity of the proposed pipelined algorithm are determined by the maximum delay time of operation of the pipeline stage. The estimates of the hardware complexity of the proposed algorithm, as well as the model of the device that implements the algorithm, are determined at the abstract and structural levels.