Page 1 of 1
Another division routine!
Posted: Sun Aug 23, 2020 9:35 pm
by 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
Re: Another division routine!
Posted: Sun Aug 23, 2020 10:19 pm
by Stonemonkey
There's something weird going on with this, I'll try to sort it out.
Re: Another division routine!
Posted: Mon Aug 24, 2020 8:26 am
by 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.
Re: Another division routine!
Posted: Mon Aug 24, 2020 9:00 am
by drogon
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
Re: Another division routine!
Posted: Mon Aug 24, 2020 11:41 am
by 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.
Re: Another division routine!
Posted: Fri Aug 28, 2020 9:03 am
by 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?