Divide 16-bit value by 8-bit constant

Basic and Machine Language

Moderator: Moderators

Post Reply
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Divide 16-bit value by 8-bit constant

Post by Mike »

During a WIP, I (re-)discovered this handy routine to do an unsigned division of a 16-bit value by an 8-bit constant:

Code: Select all

 LDA #0
 LDX #16
.loop
 ASL zp
 ROL zp+1
 ROL A
 CMP #xx
 BCC skip
 SBC #xx
 INC zp
.skip
 DEX
 BNE loop
zp and zp+1 contain the 16-bit value to be divided, and the result afterwards. The 8-bit divisor constant is encoded in the immediate fields of CMP #xx and SBC #xx. The remainder ends up in the Accumulator.

Of course, for divisors that are powers of 2, shifting/masking is shorter and faster. :)
User avatar
J.E.E.K.
Vic 20 Drifter
Posts: 23
Joined: Wed Jan 25, 2017 12:31 pm
Website: http://klasek.at/8bit
Location: AT

Re: Divide 16-bit value by 8-bit constant

Post by J.E.E.K. »

Mike wrote:[..]

Code: Select all

 LDA #0
 LDX #16
.loop
 ASL zp
 ROL zp+1
 ROL A
 CMP #xx
 BCC skip
 SBC #xx
 INC zp
.skip
 DEX
 BNE loop
zp and zp+1 contain the 16-bit value to be divided, and the result afterwards. The 8-bit divisor constant is encoded in the immediate fields of CMP #xx and SBC #xx. The remainder ends up in the Accumulator.
[..]
The routine has a serious flaw. It does not handle most significant bit of the dividend at all.
If a division routine has a divisor of 8 Bit, the subtraction has to cover 9 bits.
Try to divide $8000 by $C0, it gives a quotient of $00 and reminder $00, but should give $AA and $80.
This routine is only save for divisors less than $80 and dividends less than $8000 and taking overflows into account, the high byte of the dividend has to be less than the divisor.

The corrected version (added one line and the label .subtract):

Code: Select all

 LDA #0
 LDX #16
.loop
 ASL zp
 ROL zp+1
 ROL A
 BCS subtract  ; added: always greater if overflow into bit 9
 CMP #xx
 BCC skip
.subtract
 SBC #xx
 INC zp
.skip
 DEX
 BNE loop
Beside this, the efficiency suffers from the unnecessary shifts of the dividend. If the divisor has only 8 bit then 8 or 9 iterations are really needed (depending on how the loop is constructed). The common technique for divisions is to take the upper bytes of the dividend (to the extent of the divisor) as already shifted for subtraction.

My suggested and already tested routine is:

Code: Select all

 LDA zp+1
 CMP #xx        ; optional: check if dividend is to great
 BCS overflow   ; for a 8 bit quotient
 ASL zp
 LDX #8
.loop
 ROL A
 BCS subtract  ; added: always greater if overflow into bit 9
 CMP #xx
 BCC skip
.subtract
 SBC #xx
 SEC            ; always, because bit 9 overflow may turn the carry
.skip
 ROL zp
 DEX
 BNE loop
On exit quotient in zp, reminder in A, zp+1 unchanged.
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Divide 16-bit value by 8-bit constant

Post by Mike »

Hi, J.E.E.K.,

Thank you for correcting this oversight. I have two points to note though:
This routine is only save for divisors less than $80 and dividends less than $8000 [...]
The first restriction is correct, the second one is not. The routine in the OP works fine for all dividends $0000..$FFFF, provided the divisor is less than $80, and regardless whether the high byte of the dividend is greater than or equal to the divisor, as the routine returns the full 16 bit result.
If the divisor has only 8 bit then 8 or 9 iterations are really needed [...]
Not quite. It really depends on the (expected) size of the quotient. With one of the use cases I intended (divisor = 10 to extract decimal digits), a non-0 high byte in the result is very likely, and so this routine needs to loop over all 16 quotient bits.

If the divisor is not provided as constant, and the full 16 bit result is required it's nonetheless sensible to provide two loops, one for a 0 high byte (quotient < 256) and one for a non-0 high byte (quotient >= 256), and not just flag this as overflow.

Greetings,

Michael

P.S. I'm pulling this out of the "Tips & Tricks" thread, as my original routine has those complications I didn't take into account - and I wouldn't want to clutter up the "Tips & Tricks" thread with the follow-up discussion.

P.P.S. bug-fixed version (with credits and link to this thread here) re-instated in the "Tips & Tricks" thread. :)
Post Reply