
Trivia question for you Bill
I'm adressing this question you since I think you're probable the only one nerd enough here to know the answer but anyone is welcome to explain.<BR><BR>For some time, I've been wandering how the computer does a division.<BR><BR>I always took for granted that the computer would do the same thing I do when I make a calculation on paper but for the division I can't believe it does it as stupidly as I do.<BR><BR>When I divide for instance 10 by 2, I guess there is 5 times 2 in 10.<BR><BR>in 546 / 3, I'd start by guessing how many times 3 in 500, then in 46...etc.<BR><BR>But that's way too clumsy for a computer to do that.<BR><BR>So I've been thinking.... using >> and << (left & right logical shift) could serve as a quick calculation.<BR><BR>10 >> 2 = 5 ??<BR><BR>[binary equivalent]<BR><BR>I'll stick to 8bits for simplicity sake<BR>1010 >> 0010 = 0010 ... ?? that's not right.<BR><BR>I always sucked at binary....HELP!!<BR><BR>I wanna understand how a division is made.<BR><BR>Of course, feel free to tell me I should search on Google instead of bugging you, that would be fair but I like when you explain it, you make it sound simple :)<BR><BR>Eniac<BR><BR><BR><BR>

I know some of it
Computers can't multiply, subtract, or divide... they can only add (albeit very quickly). Division happens with recipriocals.<BR><BR>Bit shifting is okay as long as you're not on the first or the last bit, since then you'll overpass it. Also, it depends on if you're using a signed bit or not (the sign is typically the first bit).<BR><BR>Here's from MSDN:<BR><BR>These binary operators have lefttoright associativity.<BR><BR>Both operands of the shift operators must be of integral types. Integral promotions are performed according to the rules described in Integral Promotions. The type of the result is the same as the type of the left operand. The value of a rightshift expression e1 >> e2 is e1 / 2e2, and the value of a leftshift expression e1 << e2 is e1 * 2e2.<BR><BR>The results are undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand.<BR><BR>The left shift operator causes the bit pattern in the first operand to be shifted left the number of bits specified by the second operand. Bits vacated by the shift operation are zerofilled. This is a logical shift, as opposed to a shiftandrotate operation.<BR><BR>The right shift operator causes the bit pattern in the first operand to be shifted right the number of bits specified by the second operand. Bits vacated by the shift operation are zerofilled for unsigned quantities. For signed quantities, the sign bit is propagated into the vacated bit positions. The shift is a logical shift if the left operand is an unsigned quantity; otherwise, it is an arithmetic shift.<BR><BR>Microsoft Specific<BR><BR>The result of a right shift of a signed negative quantity is implementation dependent. Although Microsoft C++ propagates the mostsignificant bit to fill vacated bit positions, there is no guarantee that other implementations will do likewise.<BR><BR><BR>

RE: Trivia question for you Bill
http://www.avrasmtutorial.net/avr_en/calc/DIVISION.html<BR><BR><BR>Help any?

Since you asked...
*Essentially* all the computer does is subtract the divisor from the dividend until it gets to zero. It counts the number of subtractions, and that's then answer.<BR><BR>Now, obviously that's way too slow. So we have to use tricks.<BR><BR>I'll try a simple example.<BR><BR>45 / 5 = ??<BR><BR>convert to binary:<BR><BR>dvd is 45: 0101101<BR>dvr is 05: 0000101<BR><BR>cnt is 00: 0000000<BR>adb is 01: 0000001<BR><BR>Left shift the divisor (dvr) and the adder bit (adb) until the top most bit of dvr is 1. That is, left shift them the same number of times.<BR><BR>dvr: 1010000<BR>adb: 0010000<BR><BR>** STEPS **<BR>subtract dvr from dvd<BR>if the answer is negative, add dvr back to dvd.<BR>if the answer is positive, add adb to cnt.<BR>shift both dvr and adb one bit to the right.<BR>if adb is zero, quit.<BR>** END STEPS **<BR><BR>SO:<BR><BR>*** START ***<BR>dvd: 0101101<BR>dvr: 1010000<BR>adb: 0010000<BR>cnt: 0000000<BR><BR>subtract dvd  dvr, answer is negative, so add it back in (effectively, don't change anything)<BR>shift dvr and adb to right one bit.<BR><BR>dvd: 0101101<BR>dvr: 0101000<BR>adb: 0001000<BR>cnt: 0000000<BR><BR>subtract dvr from dvd. dvd is now 0000011<BR>so add adb to cnt. cnt is now 0001000<BR>right shift adb and dvr<BR><BR>dvd: 0000101<BR>dvr: 0010100<BR>adb: 0000100<BR>cnt: 0001000<BR><BR>subtract dvd  dvr, answer is negative, so add it back in (effectively, don't change anything)<BR>shift dvr and adb to right one bit.<BR><BR>dvd: 0000101<BR>dvr: 0001010<BR>adb: 0000010<BR>cnt: 0001000<BR><BR>subtract dvd  dvr, answer is negative, so add it back in (effectively, don't change anything)<BR>shift dvr and adb to right one bit.<BR><BR>dvd: 0000101<BR>dvr: 0000101<BR>adb: 0000001<BR>cnt: 0001000<BR><BR>subtract dvr from dvd. dvd is now 0000000<BR>so add adb to cnt. cnt is now 0001001<BR>right shift adb and dvr<BR><BR>dvd: 0000000<BR>dvr: 0000010<BR>adb: 0000000<BR>cnt: 0001001<BR><BR>adb is zero. Quit.<BR><BR>Answer is in cnt: 0001001, which is 9, decimal.<BR><BR>Okay?<BR><BR>For negative numbers, the easy way is to convert them to positive but remember what the sign of the result should be.<BR><BR>(And, as DG pointed out, the subtraction is really done by inverse addition, but that's a detail.)<BR><BR>

One typo in that...
Says:<BR>subtract dvr from dvd. dvd is now 0000011<BR>so add adb to cnt. cnt is now 0001000<BR>right shift adb and dvr<BR><BR>First line there should say:<BR>subtract dvr from dvd. dvd is now 0000101<BR><BR>(register summary below that has it right).<BR><BR>********<BR><BR>It helps if you view all that in Courier font.<BR><BR>

Geez...
How do you guys know all that....<BR><BR>Thanks a lot DG & Bill.<BR><BR>Although, I'm disapointed to realize that a computer not more clever than I am when dividing, LOL....just keep substracting until you fall below zero.<BR><BR>Well..no...actually, I'll take it on the bright side. I'm AS clever as a computer... (is that good ??)<BR><BR>LOL. Anyway, it all makes sense, thanks a lot to both of you for your time.

Should have said...
...that's just one way of doing it. Another way is to shift the dvr to the right. And there are variations.<BR><BR>

Should have said...
...that's just one way of doing it. Another way is to shift the dvd to the left. And there are variations.<BR><BR>

This is the easy stuff...
Now try coding *FLOATING POINT* division!<BR><BR>7.3311 / 38291.229718<BR><BR>and get the answer right to 53 bits of accuracy.<BR><BR>I used to do this for a living. Code multiplication and division in software. And code all the floating point ops in software (because those primitive computers didn't have *ANY* floating point hardware operations).<BR><BR>And then I got to code the SIN(), COS(), ATN(), EXP(), LOG(), and the exponentition operator ( ^ or ** depending on language ).<BR><BR>I was pretty good at it. And now it's an "art" that is dead, since it's all done in the CPUs.<BR><BR>

The best programmers..
..are those who understand mathematics. Some of the best programmers I've encountered are theoretical mathematicians, making their own programs and algorithms to do their research.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

