Divide a Binary Number

jpanhalt

Joined Jan 18, 2008
11,087
Thanks. I didn't come across that algorithm until last Fall and was thinking about writing something, but it turned out that I didn't need it. It would be interesting to compare its speed to more conventional division methods. Maybe some rainy day.

John
 

atferrari

Joined Jan 6, 2004
4,764
Thanks. I didn't come across that algorithm until last Fall and was thinking about writing something, but it turned out that I didn't need it. It would be interesting to compare its speed to more conventional division methods. Maybe some rainy day.

John
Basically, it takes longer than common ones.
 

WBahn

Joined Mar 31, 2012
29,978
I'd have to look to see if I can find it (and I'm pretty sure I could), but on the very first PIC project I ever did (on a 16C62, IIRC) I had to teach it how to do 24-bit by 24-bit fixed point multiply and divides. I believe I did the multiply by a simple shift and add operation. I think I did the same for the division using a trick I figured out (and later found in a book, but this was in 1993 or so and the internet wasn't on my radar at the time) in which I shifted the dividend around back into itself (so I didn't need additional field regsiters) and then checked and subtracted the divisor, building up the quotient in another set of field registers. The code was very small. I wasn't concerned about speed at all, so I don't know how it performed in that regard.
 

joeyd999

Joined Jun 6, 2011
5,234
For fun and comparison, here's my 32 bit IEEE float divide routine. It's part of a larger framework of my stack-based floating point math library (PIC18):

Code:
;*****************************************
;** DIVF -- Divide wreg3 = wreg1 / wreg2   **
;*****************************************

divf    movff    bsr,tmpbsr        ;save program BSR
    BANKSEL    wreg1            ;set bsr for float working space

    movlw    1            ;2 operands
    rcall    getoper            ;  get from stack

    clrf    wtmpe+0
    clrf    wreg3+0            ;clear quotient
    clrf    wreg3+1
    clrf    wreg3+2

    movf    wreg1s,w,1        ;get status
    xorwf    wreg2s,w,1        ;compute result sign
    andlw    1            ;mask it
    movwf    wreg3s,1        ;save new sign

    bbs    wreg1s,FLNAN,1,fretnan    ;NAN / (any) = NAN
    bbs    wreg2s,FLNAN,1,fretnan    ;(any) / (NAN) = NAN
    bbs    wreg1s,FLZERO,1,fretz    ;0 / (any) = 0
    bbs    wreg2s,FLZERO,1,fretinf ;(any) / 0 = INF
    bbs    wreg2s,FLINF,1,fretz    ;(any) / INF = 0
    bbs    wreg1s,FLINF,1,fretinf    ;(INF) / (any) = INF

    clrf    wtmpd+0,1
    clrf    wtmpd+4,1
    clrc
    rrcf    wreg1+2,w,1        ;put wreg1 >> 1 into wtmpd
    movwf    wtmpd+3,1
    rrcf    wreg1+1,w,1
    movwf    wtmpd+2,1
    rrcf    wreg1+0,w,1
    movwf    wtmpd+1,1
    rrcf    wtmpd+0,f,1

dfninf    movf    wreg2e,w,1        ;get exponent of divisor
    subwf    wreg1e,w,1        ;  subtract from dividend
    addlw    33            ;  and offset for loops
    movwf    wreg3e,1        ;  save

dfloop    movf    wreg2+0,w,1        ;subtract divisor
    subwf    wtmpd+1,w,1
    movwf    wtmpe+1,1

    movf    wreg2+1,w,1        ;subtract divisor
    subwfb    wtmpd+2,w,1
    movwf    wtmpe+2,1

    movf    wreg2+2,w,1        ;subtract divisor
    subwfb    wtmpd+3,w,1
    movwf    wtmpe+3,1

    clrw
    subwfb    wtmpd+4,w,1
   
    bm    dfneg            ;result negative?

    movwf    wtmpd+4,1        ;no, save back remainder
    movff    wtmpe+3,wtmpd+3
    movff    wtmpe+2,wtmpd+2
    movff    wtmpe+1,wtmpd+1

dfneg    rlcf    wtmpe+0,f,1
    rlcf    wreg3+0,f,1        ;roll bit into quotient
    rlcf    wreg3+1,f,1
    rlcf    wreg3+2,f,1

    rlcf    wtmpd+0,f,1        ;rotate divisor
    rlcf    wtmpd+1,f,1
    rlcf    wtmpd+2,f,1
    rlcf    wtmpd+3,f,1
    rlcf    wtmpd+4,f,1

    decf    wreg3e,f,1
    btfss    wreg3+2,7,1        ;are we done?
    bra    dfloop            ;no

    movlw    0x80            ;round result
    addwf    wtmpe,f,1
    clrw
    addwfc    wreg3+0,f,1
    addwfc    wreg3+1,f,1
    addwfc    wreg3+2,f,1

    bra    fretflt            ;fix result
 

MrAl

Joined Jun 17, 2014
11,389
Hi,

Working in the IEEE format is easier but here is the simplest method for dividing in pure binary. This works very easily because of the fact that it is binary and that means there are extreme limits on the values a single number can take on (0 or 1) and that in turn means there are extreme limits on the mathematics unlike what we are used to seeing in base 10.

To illustrate, we'll divide 72 by 12.
In division, the dividend is often placed under a line where the quotient is placed above the line, and the divisor is placed ahead of the dividend. Here however i'll show the quotient to the RIGHT of the dividend and the divisor to the LEFT of the dividend. Thus if we had 6 divided by 2 equals 3 it would look like:
2, 6, 3

I am doing it that way because it's much easier to write out.

Ok, so now 72 div by 12 in binary.

First, 72 in binary is 1001000, and this can be found using various algorithms.
Also, 12 in binary is 1100, so now let's start...

1100, 1001000

First, we match up the leading 1's in both of these numbers, then subtract. When we subtract we subtract the same number of digits in the dividend as there are in the divisor, so we subtract 1001-1100. Note we are only using four of the digits of the dividend because there are only four in the divisor.
Now there are only, lo and behold, two possibilities for the subtraction:
1. We get a negative number.
2. We get a positive number or zero.
If we get a negative number then the next digit in the quotient is a zero, and if we get anything else the next digit is a 1. So we have our first digit, a zero: 0. We have now so far:
1100, 1001000, 0

Now since we got a zero, we do another subtraction but this time with more digits from the dividend. This means we have to subtract; 10010-1100. Doing that we get 110. This is positive so the next digit is 1, and we have now:
1100, 1001000, 01

We've only used the 10010 part of the dividend so far, so next we bring down the next zero in the complete dividend (next to last zero) and tack it onto the end of the subtraction result 110 and we get 1100.

The next subtraction is 1100-1100 which results in zero, so the next digit is also a 1 and we now have:
1100, 1001000, 011

The result was zero, or 000, so we bring down the last zero and we get 0000, and since 0000-1100 is negative, the next digit is zero and we now have:
1100, 1001000, 0110

We've used up the last digit in the dividend, so if we dont want fractional digits we are done, although we would not get any here anyway because 12 divides into 72 with no remainder.

The last quotient was 0110, which in base 10 is 6, which is the answer to 72 divided by 12.

The included snapshot shows how this is done on paper. It's almost like dividing in base 10 except there are less possibilities which actually makes it easier to do.

A couple things to note:
1. We never divide anything, just subtract.
2. The sign of the subtraction result alone tells us if the next digit in the quotient is a 1 or 0. If it is positive or zero then the next digit is 1, if negative the next digit is 0.
 

Attachments

Last edited:

merts

Joined Apr 1, 2016
8
i assume that you really want to devide and not a circuit to devide.
You gave two examples.Work in the base you are most comfortable with.
72/12 =6 = 110 binary. 100/5 = 20 =10100 binary.
 

WBahn

Joined Mar 31, 2012
29,978
i assume that you really want to devide and not a circuit to devide.
You gave two examples.Work in the base you are most comfortable with.
72/12 =6 = 110 binary. 100/5 = 20 =10100 binary.
I suspect that the point of the assignment was to do the math in binary and not to just convert the answer done in decimal to binary at the end.

As indicated in a much earlier response, if his son knows how to do long division in base ten, then this should not present much of a problem at all since the long-division algorithm is completely base-agnostic.
 

hp1729

Joined Nov 23, 2015
2,304
I suspect that the point of the assignment was to do the math in binary and not to just convert the answer done in decimal to binary at the end.

As indicated in a much earlier response, if his son knows how to do long division in base ten, then this should not present much of a problem at all since the long-division algorithm is completely base-agnostic.
Some people imagine things to be harder than they really are. Yes, division is the same in any base number system.
 

atferrari

Joined Jan 6, 2004
4,764
Some people imagine things to be harder than they really are. Yes, division is the same in any base number system.
At concept level, no doubt, but binary, specifically, allows shifts effectively implemented, for example, for quotient and reminder in a single operation.
 

atferrari

Joined Jan 6, 2004
4,764
Keep in mind that the TS was specifically referring to pen and paper computations.
OK William. Sure I had that in mind. To reduce what could be a long thread inside a thread, could you show a concrete example of what you believe would be your concrete example for the TS / OP as an answer?
Let us say, to divide these two (decimal values): 237 / 18?
 

WBahn

Joined Mar 31, 2012
29,978
OK William. Sure I had that in mind. To reduce what could be a long thread inside a thread, could you show a concrete example of what you believe would be your concrete example for the TS / OP as an answer?
Let us say, to divide these two (decimal values): 237 / 18?
It would be a lot easier with a monospace font or even a CODE block in which I can paste text while preserving formatting or even if I could SEE the code formatting without having to do a preview. But here goes:

237 => 11101101
18 +> 10010

Code:
           1101r11
      ---------
10010 )11101101
       10010
       -----
        10111
        10010
        -----
          10101
          10010
          -----
             11
 

jpanhalt

Joined Jan 18, 2008
11,087
I learned this morning there is a "text" table format and how to use it for tables with the | operator. Maybe there are operators to let you do what you want to do with text.
In the interim, why not just copy one of the many examples on the Internet for how to do binary division?
upload_2016-5-29_17-35-8.png

Alternatively, do it with whatever tools you are comfortable with and use the clip tool.

John

Edited 6:17 PM EDT
 
Last edited:

WBahn

Joined Mar 31, 2012
29,978
In the interim, why not just copy one of the many examples on the Internet for how to do binary division?
I didn't know how long it might take me to find an example on the Internet that divides 237 by 18 in binary.

Alternatively, do it with whatever tools you are comfortable with and use the clip tool.
I thought about doing that, but I prefer to post original source for stuff like this when possible so that it can be quoted and edited if desired. An alternative would have been using TeX, but dealing with alignment is more than a bit of a pain.
 

jpanhalt

Joined Jan 18, 2008
11,087
@WBahn

Sorry for the mistake on my part. I meant Table and have corrected the post. However, given the sophistication of XenForo, I would be surprised if there are not better formatting tools for text. Bertus helped me this morning and introduced me to the | operator for tables.

John
 

WBahn

Joined Mar 31, 2012
29,978
Most of the bells and whistles are in the form of add-ins. I'm sure that lots of add-ins exist for stuff like this, but every add-in that jrap incorporates is one more that is a source of work and frustration for him.

I liked the Table formatting options that were available under vB quite a bit more -- and there were more of them. But it is what it is.
 

joeyd999

Joined Jun 6, 2011
5,234
Most of the bells and whistles are in the form of add-ins. I'm sure that lots of add-ins exist for stuff like this, but every add-in that jrap incorporates is one more that is a source of work and frustration for him.

I liked the Table formatting options that were available under vB quite a bit more -- and there were more of them. But it is what it is.
I wish @jrap would fix the code tags to have user defined tab sizes. Oops. This isn't the off-topic or suggestions forum, is it?...
 
Top