Browse Prior Art Database

Fast Division Using Table Look-Up

IP.com Disclosure Number: IPCOM000102432D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 2 page(s) / 62K

Publishing Venue

IBM

Related People

Palmer, MJ: AUTHOR

Abstract

Described is a method of converting a 'Logical Block Address' to cylinder track and sector values on a microprocessor without a divide instruction. After breaking the dividend into bytes, look-up tables are used to find quotients and remainders. Carries are used while computing the remainder to adjust the quotient. Speed is gained at the expense of table space.

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

Fast Division Using Table Look-Up

       Described is a method of converting a 'Logical Block
Address' to cylinder track and sector values on a microprocessor
without a divide instruction.  After breaking the dividend into
bytes, look-up tables are used to find quotients and remainders.
Carries are used while computing the remainder to adjust the
quotient.  Speed is gained at the expense of table space.

      Microprocessors which do not have a built-in divide instruction
need software algorithms to perform division. These are usually
implemented as a loop, containing subtraction and shifting
operations, executed as many times as there are bits in the dividend
and, in consequence, are slow.  When the divisor is a known constant
and if execution time is critical, a faster algorithm is required.

      An example is when dividing a logical block address (LBA)
received in a SCSI command by the number of sectors per cylinder, to
get the cylinder address.  The remainder of the division is then
further divided by the number of heads, to get the track and sector
numbers.

      The advantages of this algorithm are fast execution with both
quotient and remainder generated.  When dividing an N-byte number
(the dividend) by a given constant divisor (K), the dividend is first
split up into N parts, at byte boundaries.
      Example:  (N=3)
                '123456'x = '120000'x + '3400'x  + '56'x
                             i2='12'x    i1='34'x  i0='56'x

      Each index i is then used as an index into a table of 256
entries which gives both the quotient and remainder when that part of
the dividend is divided by di...