Browse Prior Art Database

Fast Division by 5 in Hardware for Frame Buffer Computations

IP.com Disclosure Number: IPCOM000112503D
Original Publication Date: 1994-May-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 118K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

The use of frame buffers whose resolutions are multiples of 5, e.g., 1280, 1600, etc., makes it sometimes necessary to perform divisions by 5. One case would be when 5 memory banks are utilized to represent the frame buffer. In order to update the frame buffer it is necessary to determine which bank to write to, which requires a modulo 5 operation and which location to write to within the bank which requires a divide by 5 operation.

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

Fast Division by 5 in Hardware for Frame Buffer Computations

      The use of frame buffers whose resolutions are multiples of 5,
e.g., 1280, 1600, etc., makes it sometimes necessary to perform
divisions by 5.  One case would be when 5 memory banks are utilized
to represent the frame buffer.  In order to update the frame buffer
it is necessary to determine which bank to write to, which requires a
modulo 5 operation and which location to write to within the bank
which requires a divide by 5 operation.

      An existing solution to this problem is to use a divide and
conquer approach.  The divisor is expressed as a sum of of a specific
set of smaller numbers.  For example, 36 = 32 + 4.  The exact
remainders and quotients for division by 5 for these numbers is
hardwired with special circuits.  Then

  36/5 = (32 + 4)/5 = 32/5 + 4/5 = 6 + 0 + (6/5) =  6 + 1 = 7.

      The problem with this method is that it requires a considerable
amount of hardware which increases significantly as the divisor
increases.  Moreover its time complexity may depend on the number of
1s in the binary representation of the divisor.

Therefore we attempt to produce a more economical solution.

      NEW ALGORITHM - We want to determine x/5 and x mod 5 where x is
an integer.  The main idea here is that division by a power of two is
simple in hardware and therefore it would be advantageous to
represent 5 by an approximation 5 approx a/2**k where both a and k
are integers.  Let b = (x X a)/2**k.  Then y = x/5 approx b.

      We need to determine a and k so that y = b for the range of x
we are interested in.

Then x mod 5 = x - b X 5 = x - (b X 2 X 2) - b.

      Let c_{f} = 2**k/a where c_{f} is a floating point number.  Let
b_{f} = x/c_{f} where c_{f} is a floating point number.  We need to
make c_{f} as close to 5.00 as possible.  If c_{f} > 5.00 then b_{f}
will be less than b and a large error will occur due to truncation.
If on the other hand c_{f} < 5.00 then b_{f} will be greater than b
and the error due to truncation will be acceptable.  For example
10/5.02 will give 1 which is uncacceptable whereas 10/4.98 will give
2 which is the desired result.

  2**k & Best a &   a/2**k    & 5 - a/2**k & Max x without error
 ------------------------------------------------------------------
       64 |     13 |  4.923076923 | 0.076923077 |        63
     1024 |    205 |  4.995121951 | 0.004878049 |      1023
     8192 |   1639 |  4.998169616 | 0.001830384 |      2733
    16384 |   3277 |  4.999694843 | 0.000305157 |     16383
   131072 |  26215 |  4.999885562 | 0.000114438 |     43963
   262144 |  52429 |  4.999980927 | 0.000019073 |    262143

Table 1.  Table of approximations

      Table 1 shows the possible approximations that can be used.
Note that there is no entry for 2**k = 128, or for 2**k = 256, etc.
This means that there is no better solution for 2**k...