Another division routine!

[Stonemonkey]

I'm looking at ways to divide and come up with this, it's unsigned 16/16=16 bits and doesn't give a remainder. Not fully tested so maybe some errors somewhere but it seems to work so far. I tried this after reading a comment about non restoring division changing the sign of the divisor. Is this any use, could it be improved at all, or should I try something else?

Code: Select all

/zero page
.p EQUW &0000 /divisor
.m EQUW &0000 /code uses this space
.v EQUD &00000000 /dividend in low 16 bits/result in low 16 bits

/code
.divide      SEC
             LDA #&00
             STA v+2
             STA v+3
             SBC p
             STA m
             LDA #&00
             SBC p+1
             STA m+1
             LDY #&10
             LDX #&02
.loop              ASL v+0
                   ROL v+1
                   LDA v+2
                   ROL A
                   ROL v+3
                   CLC
                   ADC p+0,X
                   STA v+2
                   LDA v+3
                   ADC p+1,X
                   STA v+3
                   LDX #&00
                   BCC under
                          LDX #&02
                          INC v+0
.under              DEY
              BNE loop
              RTS

[Stonemonkey]

There's something weird going on with this, I'll try to sort it out.

[barrym95838]

Multiplication and division can be a bit tricky to get right on the first or even second try, and I applaud your efforts to get right down to the nuts and bolts. I have a smaller and more featureful version from my VTL02 interpreter, but I didn't write it from scratch ... I adapted it from some older 6800 code that I found. I'm not going to claim that mine's any better than anyone elses, although it has been battle-tested, and seems to perform adequately. You are welcome to adapt it to your use case, although I certainly understand that you might be more interested in something you've built yourself from the ground up.

Code: Select all

;-----------------------------------------------------;
; 16-bit x 16-bit unsigned division routine
;   var[x] /= var[x+2], remn = remainder
;   var[x] /= 0 produces remn = var[x], var[x] = 65535
; 40 bytes
div:
    lda  #0
    sta  remn       ; remn = 0
    sta  remn+1
    ldy  #16        ; loop counter
div1:
    asl  0,x        ; var[x] is gradually replaced
    rol  1,x        ;   with the quotient
    rol  remn       ; remn is gradually replaced
    rol  remn+1     ;   with the remainder
    lda  remn
    cmp  2,x
    lda  remn+1     ; partial remainder >= var[x+2]?
    sbc  3,x
    bcc  div2
    sta  remn+1     ;   yes: update the partial
    lda  remn       ;     remainder and set the
    sbc  2,x        ;     low bit in the partial
    sta  remn       ;     quotient
    inc  0,x
div2:
    dey
    bne  div1       ; loop 16 times
    rts

To use mine, you reserve two bytes at remn, load the dividend and divisor into four consecutive zero-page bytes, point register X to the first of those bytes and let 'er rip. If you don't need the remainder you may be able to shorten this a bit further, but I'll leave that as an exercise for the interested reader.

[drogon]

Stonemonkey wrote:

I'm looking at ways to divide and come up with this, it's unsigned 16/16=16 bits and doesn't give a remainder. Not fully tested so maybe some errors somewhere but it seems to work so far. I tried this after reading a comment about non restoring division changing the sign of the divisor. Is this any use, could it be improved at all, or should I try something else?

I've not looked at your code (yet), however have you seen this?

http://nparker.llx.com/a2/mult.html

I initially used it as the basis for my own 32-bit MUL and DIV instructions in my BCPL system.

My strategy for signed division (and multiplication) involves working out the sign of the result, making both sides positive, doing the operation then fixing the sign of the result.

-Gordon

[Stonemonkey]

Hi barrym and Gordon, thanks, I'll look through that.

Gordon, I'll be doing that when it comes to signed division, the negating at the start is so I have a positive and negative divisor value either of which is used for the addition depending on the previous pass through the loop.

[Stonemonkey]

Hi, I don't have my code to hand right now but what I've done is break that up into 2 * 8 loops so only 3 rotates are required in each loop and I've got rid of the increment as the carry is carried back to the start of the loop.
So I've got 2 loops like this:

Code: Select all

.loop ROL v+1
LDA v2
ROL A
ROL v3
CLC
ADC lo,X
STA v2
LDA v3
ADC hi,X
STA v3
LDX #&00
BCC skip
INX
.skip
DEY
BNE loop

X only ever contains either 0 or 1 to index the addition and I want to set it to C at the end of the loop, is there any better way to do that than what I have?