Hey all - just trying to get Bregalad's division routine to work for one of my purposes. If you're unfamiliar, it is:
Code:
;8-bit divide
;by Bregalad
;Enter with A = Dividend, Y=Divisor
;Output with YX = (A/Y) << 8, A = remainder
Division
sta Dvd ;Stores dividend
sty Dvs ;Stores divisor
ldy #$00
sty ResHi ;Clear result, setting up a ring counter
iny ;by initializing the result to $0001.
sty Res ;When the 1 gets shifted out, we're done
ldy #$10 ;The loop is for 16-bit result
- asl Dvd
rol A ;Shift divisor in 1 bit
bcs + ;If carry is set, the dividend is already greater
cmp Dvs ;Check if fractional dividend is greater than divisor
bcc ++
+ sbc Dvs ;Subtract (C is always set)
++ rol Res ;Shift result (1 if subtraction was done, 0 otherwise)
rol ResHi
bcc -
;; Res is now low bit of desired value
;; ResHi is now high bit of desired value
rts
I have slightly altered this so that I actually use Res and ResHi in my next calculation, rather than pushing them to x and y. But Res and ResHi are not returning expected results. When I put 1 into dividend and 2 into divisor, I'd expect to get res = #$80 and ResHi = #$00, correct?
Anyone see any issue?
Did the original routine work correctly? Could you post that so we can compare?
One strange thing I noticed is that even though you're using a ring counter, you're still loading Y with $10 like you were going to count down from 16, but then you don't touch Y again. This isn't affecting the result, but could be a sign that something was not changed correctly.
I pulled straight from here:
http://wiki.nesdev.com/w/index.php/8-bit_DivideThe only thing that's different is that rather than pushing Res and ResHi to x and y at the end, I just leave them as is. I know that's not the issue, but even just in case, in coming back from the routine, I debugged for the values, and Res = FE while ResHi = FF...definitely not correct.
I do see this as an issue, for sure...(the Y), but I'm not sure how to append Bregalad's code to get this to work correctly.
Thanks!
**EDIT** - also open to other methods to solving this.
But did you actually try the unmodified routine to make sure it works? If it doesn't, we definitely should fix that, since that would mean the wiki is giving out wrong information.
I guess the ldy #$10 is just a leftover from before the code used a ring buffer.
I'll see if I can spot the bug, but my debugging capabilities are very limited right now as I'm on my phone.
Code from FF1
On input:
'battlereward' is the dividend (2 bytes)
'@divisor' is the divisor
On output:
'battlereward' is the quotient (2 bytes)
'@remainder' is the remainder
Code:
STY @divisor ; Y (the number of surviving party members) is the divisor
LDA #$00
STA @remainder ; zero remainder
LDX #16 ; loop 16 times, one for each bit of the dividend
ROL battlereward ; roll out the high bit of the sum into C
ROL battlereward+1
@DivLoop:
ROL @remainder ; roll bit into remainder
LDA @remainder
CMP @divisor
BCC :+ ; once the remainder >= divisor
SBC @divisor ; ... subtract divisor
STA @remainder
: ROL battlereward ; roll 1 into result (if subtracted)
ROL battlereward+1 ; or 0 into result (if didn't subtract)
DEX
BNE @DivLoop
RTS
EDIT:
My comments are slightly wrong. The loop actually only runs 15 times -- which is why battlereward is rotated once before the loop starts.
EDIT 2:
Crap I just realized that the routine you're using is different and is generating a fixed point result rather than quo+rem result. Whoops! Oh well. =x
tokumaru - I have now just made a routine to test the 8-bit divide routine exactly as is just to see what I get as a result. it is verbatim the routine in the wiki. I feed it 1 as a dividend and 2 as a divisor. Then I debug read the x and y values. The result is the same as it was in my customization.
Anyone else have a thought on this? How to fix it, or possibly an alternative division routine to achieve this purpose?
Thanks.
****EDIT****
Here are some results:
If I seed the dividend with 1 and the divisor with 2, I get (the opposite, but seemingly predictable at least, of) what I would expect:
Res = 0
ResHi = 80
If I seed the dividend with 2 and the divisor with 2, I get (not intuitive...though I suppose 2 in a high byte minus ff in a low byte might give me 1, the expected amount?):
Res = 2
ResHi = FF
If I seed the dividend with 4 and the divisor with 2, I get (this should definitely not return the same as above case...):
Res = 2
ResHi = FF
If I seed the dividend with 8 and the divisor with 2, I get:
Res = 2
ResHi = FF
I I seed the dividend with 1 and the divisor with 8, I get (back to what I expect):
Res = 0
ResHi = 20
The problem seems to be when the dividend is equal to or larger than the divisor. Does the case analyses help anyone spot an issue?
JoeGtake2 wrote:
or possibly an alternative division routine to achieve this purpose?
Well you could use the one from FF1 that I posted. The only [functional] difference is that you'd effectively put your dividend in the high-byte of the input and would zero the low byte -- and then you discard the remainder.
Here's a modified version which does that and removes the unnecessary 'remainder' variable (it just keeps the value in A)
Code:
; INPUT: dividend (1 byte)
; divisor (1 byte)
;
; OUTPUT: quotient+0 = "fractional" part of result
; quotient+1 = "whole number" part of result
Divide:
LDA dividend
STA quotient+1
LDA #$00
STA quotient+0
LDX #16
ROL quotient
ROL quotient+1
Divide_Loop:
ROL A
CMP divisor
BCC :+ ; once the remainder >= divisor
SBC divisor ; ... subtract divisor
: ROL quotient ; roll 1 into result (if subtracted)
ROL quotient+1 ; or 0 into result (if didn't subtract)
DEX
BNE Divide_Loop
RTS
As I understand it, to get the fractional part of a division you just have to keep shifting and subtracting after the integer quotient had already been found, isn't it?
The fractional part is just continuing with division for digits beyond the '1s' digit.
Just like in long division. To find the places past the decimal, you just keep doing what you're doing for however many more digits you want.
In practice, if you want X bits of fraction, just left-shift the dividend by X.
Ex:
1 / 2 becomes $0100 / 2 which = $0080
Thanks for the help - but this routine still gives me unexpected results.
Again, to test, I just directly fed it values, and immediately read the return values after the division routine in debugger. Here are my test results:
Input:
Dividend:1
Divisor:1
Expected Result:
Quotient:00
Quotiont+1: 01
Actual Result:
Quotient:40
Quotient+1:00
Input:
Dividend:1
Divisor:2
Expected Result:
Quotient:00
Quotient+1:80
ActualResult:
Quotient:20
Quotient+1:00
Input:
Dividend:2
Divisor:1
Expected Result:
Quotient: 2
Quotient+1: 00
Actual Result:
Quotient:00
Quotient+1:80
Literally, this is directly feeding the code you suggested with values and reading the outputs - no other things are involved, and those are the results I get.
Any thoughts on this? Do I have some fundamental misunderstanding of the results I should be getting? Does the pattern outlined above give any thoughts as to what may be wrong?
(also, noting with the last example that perhaps the dividend and divisor were inverted somehow, I tried dividend 4, devisor 1 expecting to get 00 and 40 respectively, however I get 00 and 00...so that ruled that out...)
Okay so that first ROL should be an ASL. I don't know why it was a ROL... whoops!
After correcting that...
an actually testing it (which I didn't do before =x) it seems to now be working.
Sorry for the confusion.
Code:
#org 0, 0, 16, 0
#byte 'NES', $1A, 1, 0
#org $C000, $10, $4000, 0
quotient = 0
dividend = 2
divisor = 3
Reset:
lda #1
sta dividend
sta divisor
jsr Divide ; quotient: 00 01 as expected (1/1 = 1)
lda #1
sta dividend
lda #2
sta divisor
jsr Divide ; quotient: 80 00 as expected (1/2 = 0.5)
lda #2
sta dividend
lda #1
sta divisor
jsr Divide ; quotient: 00 02 as expected (2/1 = 2)
jmp Reset
Divide:
LDA dividend
STA quotient+1
LDA #$00
STA quotient+0
LDX #16
ASL quotient ; <- should be ASL
ROL quotient+1
Divide_Loop:
ROL A
CMP divisor
BCC :+ ; once the remainder >= divisor
SBC divisor ; ... subtract divisor
: ROL quotient ; roll 1 into result (if subtracted)
ROL quotient+1 ; or 0 into result (if didn't subtract)
DEX
BNE Divide_Loop
RTS
#pad $FFFA, 0
#word Reset, Reset, Reset
I am mesmerized that this is still not giving me the right values. I'm even attempting to HARD CODE the values as part of the routine, and still getting weird results...
I will type exactly what I have:
Code:
Divide:
LDA #$02
STA dividend
LDA #$01
STA divisor
LDA dividend
STA quotient+1
LDA #$00
STA quotient
LDX #$16
ASL quotient
ROL quotient+1
DivideLoop:
ROL A
CMP divisor
BCC skip+
SBC divisor
skip+:
ROL quotient
ROL quotient+1
DEX
BNE DivideLoop
;;;;; and to read in debugger what I come up with........
LDA quotient
STA $07ff
LDA quotient+1
STA $07ff
RTS
Even doing it that way, I still get the same funky results as before.
Do you see any mistake? Also, question - it seems you set up quotient, dividend, and divisor up as constants with rather arbitrary values that get changed in the reset function, while mine are ram variables...i can't imagine that would have anything to do with it, but it's the only difference that I see....
"LDX #$16" is wrong... that should be "LDX #16" or "LDX #$10"
You're also writing both bytes of the quotient to $07FF ... so they'll be overwriting each other.
EDIT:
Quote:
Also, question - it seems you set up quotient, dividend, and divisor up as constants with rather arbitrary values that get changed in the reset function, while mine are ram variables
No, they're variables in my code.
"quotient = 0" tells the assembler that the name 'quotient' is to be resolved to the numerical value of 0
So
Code:
LDA quotient
becomes:
Code:
LDA 0 ;notice: direct page mode... NOT immediate mode
Essentially, I'm saying "I want my quotient variable at address 0, and I want dividend at address 2"
*smacks head*.........
yes. I'm sure it's the #$16.
Ouch.
That seems to have been it. Wow. That's almost too painful...hahahaha. *eyers are bleary*
(and the 07ff writes were what i was plucking the writes to from the debugger....so i could read the output values both in a row...that's not where they end up in the actual code)
Yay!
Glad it's working.
Disch wrote:
Okay so that first ROL should be an ASL. I don't know why it was a ROL... whoops!
After correcting that...
an actually testing it (which I didn't do before =x) it seems to now be working.
Sorry for the confusion.
Code:
#org 0, 0, 16, 0
#byte 'NES', $1A, 1, 0
#org $C000, $10, $4000, 0
quotient = 0
dividend = 2
divisor = 3
Reset:
lda #1
sta dividend
sta divisor
jsr Divide ; quotient: 00 01 as expected (1/1 = 1)
lda #1
sta dividend
lda #2
sta divisor
jsr Divide ; quotient: 80 00 as expected (1/2 = 0.5)
lda #2
sta dividend
lda #1
sta divisor
jsr Divide ; quotient: 00 02 as expected (2/1 = 2)
jmp Reset
Divide:
LDA dividend
STA quotient+1
LDA #$00
STA quotient+0
LDX #16
ASL quotient ; <- should be ASL
ROL quotient+1
Divide_Loop:
ROL A
CMP divisor
BCC :+ ; once the remainder >= divisor
SBC divisor ; ... subtract divisor
: ROL quotient ; roll 1 into result (if subtracted)
ROL quotient+1 ; or 0 into result (if didn't subtract)
DEX
BNE Divide_Loop
RTS
#pad $FFFA, 0
#word Reset, Reset, Reset
Hello Disch,
I believe the routine can be further optimized to this:
Code:
Divide:
LDA dividend
ASL A
STA quotient+1
LDA #$00
STA quotient+0
LDX #16
Divide_Loop:
ROL A
CMP divisor
BCC :+ ; once the remainder >= divisor
SBC divisor ; ... subtract divisor
: ROL quotient ; roll 1 into result (if subtracted)
ROL quotient+1 ; or 0 into result (if didn't subtract)
DEX
BNE Divide_Loop
RTS
It saves 3 bytes and 8 cycles by removing the "ASL quotient" and "ROL quotient+1" outside of the loop and adding a single "ASL A". I haven't tested this routine, but believe it works.