Browse Prior Art Database

Determination of Odd/Even Quotient without Division

IP.com Disclosure Number: IPCOM000115699D
Original Publication Date: 1995-Jun-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Related People

Hodges, P: AUTHOR

Abstract

A method is disclosed by which the result of division by a constant is determined to be either even or odd without actual division. Only the simple operations of dividing by a power of two and addition are used. The procedure requires iteration on the following:

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 60% of the total text.

Determination of Odd/Even Quotient without Division

      A method is disclosed by which the result of division by a
constant is determined to be either even or odd without actual
division.  Only the simple operations of dividing by a power of two
and addition are used.  The procedure requires iteration on the
following:

         Consider divisor D and dividend C.
  Let P1 be a selected power of 2 and divide P1 by the constant D:
    P1 = DxK1 + R1.
  Divide C by P1:
    C = P1xA1 + B1
      = (DxK1  + R1)xA1 + B1
      = DxK1xA1 + R1xA1 + B1
      = Dx(K1xA1) + C1           where C1 = R1xA1 + B1.

      In each iteration, the value of Ci = (RixAi + Bi) from the
previous iteration is substituted for the original value of C.  The
power of 2 used as a divisor is reduced in successive iterations,
although More than one iteration at a particular power of 2 may be
required.  Iteration continues until Ci < 2D.
  Finally, there is:
    C = Dx(K1xA1 + K2xA2 + ... + Kn x An) + Cn, if Cn < D
    C = Dx(K1xA1 = K2xA2 + ... + Kn x An + 1) + Cn', if Cn = D + Cn'.

      Selecting those Ai for which Ki is odd, the result of division
by D is odd or even according to the parity of the low order bits of
the selected Ai's, plus the additional 1 in case of Cn = D + Cn'.

This parity value can be accumulated during iteration, and it is not
necessary to retain the actual values of the Ai.

The procedure is illustrated for division o...