=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    Date: Thu, 28 Oct 1999  13:21:55
    From: "Nikolai Golovchenko" 
      To: "pic microcontroller discussion list" 
 Subject: Re:      Re: 16-BIT DIVISION
--------------------------------------------------------------------------------

Hey, I guessed!
If you have to divide or multiply a number by a constant there is a
possibility to optimize this routine for the given constant. Multiplication
and division are treated the same, because the constant can be fractional
and regarded as multiplier in both cases.

Example:
Assume constant multiplier c=3.578 and variable v is 16 bit long.

Step1. Convert c to binary fractional form:
3.578(dec) = 11.1001 0011 1111 0111 1100 ...(bin)

Step2. Replace series of ones with difference
All series of two and more one's can be replaced by differences. For
example, 1111 = 10000 - 1. The difference requires only one substraction
instead of four additions.
If there are no such series than optimization not possible.
3.578(dec) = 100.0001 0100 0000 0000 0000..(bin)
                       - 0.1000 0000 0000 0000 0100..(bin) =
= 4 - 1/2 + 1/16 + 1/64 - ...(dec).

Step3. Limit fractional part of positive and negative constant multiplier to
16-1 bits. 16th bit can be used to round multiplication result.
3.578 = 4 - 1/2 + 1/16 + 1/64

Step4.Now shift v and add and sub...... ;)


Am I right?

Bye.
Nikolai