Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
???
03/03/09 10:01
Read: times


 
#163017 - Division is shift and compare
Responding to: ???'s previous message
You may iterate this problem with shift and compare.

Figure out integer part:
How many times can you divide 0624h by 0C49?
0, so no subtraction.

Now, shift the divisor left one step
0624h <<= 1 = 0C48h
Current weight 0.5.

How many times can you divide 0C48h by 0C49h?
0, so no subtraction, and no addition of weight.

Now, shift the divisor left one step.
0C48h <<= 1 = 1890h
Current weight 0.25.
How mny times can you divide 1890h with 0C49h?
Since you are stepping one bit at a time, the answer will always be 0 or 1.
In this case, the number is at least large enough, so the answer is 1.
Add current weight 0.25 to your result - now you have 0.25.
Subtract divident: 1890h - 0C49h = 0C47h.

Now, shift the divisor left one step.
0C47H <<= 1 = 188Eh
Current weight 0.125
How many times can you divide 188E with 0C49h.
One time, so add 0.125 to your result - now you have 0.375.
Subtract dividend and shift left: (188E - 0C49) << 1 gives 188A

188A >= 0C49, so divides 1 time.
Current weight was 0.0625, so your current result is 0.375 + 0.0625 gives 0.4375.
Subtract and shift: (188A - 0C49) << 1 gives 1882.

1882 >= 0C49, so divides 1 time.
Current weight was 0.03125 so 0.4375 + 0.03125 gives 0.46875.
Subtract and shift: (1882 - 0C49) << 1 gives 1872.

Repeat until the subtract results in zero, or you have enough number of value digits in your answer.

When workig with integers, you have to decide how you like your answer. Either scale it with a constant and use fixed point arithmetic, i.e a scaling of 10000 gives:
10000 represets 1.
5000 represents 0.5
1000 represents 0.1
...
The closest you would get to 1 from below would be 9999, representing 0.9999.
So you would then add 2500 + 1250 + 625 + .. to form your result.

Or you may decide that you want your answer to be a fractions, i.e each 0.5 represented by a bit.

Say a 32-bit integer as answer on the format 16.16, i.e. the high 16 bits are integer part, and the low 16 bits are fractional part. The fractional values to add would then be:
32768 represets 0.5
16384 represents 0.25
8192 represets 0.125
4096 represets 0.0625
...
The closest you get to 1 frow below will be 0x0000ffff

Note that the first comparison above, computing the integer part, isn't limited to a divisability of 0 or 1. So you may have to do the reverse when finding the integer part - you may have to multiply your dividend (0C49h) by two a number of times until it is about to shift out high-end bits or until it is larger or iqual to the divisor. Or if your processor has a big enough div instruction, you may let the processor compute the integer part of the division.

List of 3 messages in thread
TopicAuthorDate
32 or 16 bit division            01/01/70 00:00      
   Suggest 8052.com Code Library            01/01/70 00:00      
   Division is shift and compare            01/01/70 00:00      

Back to Subject List