ADVENTURES IN DIVISION BY 10

QUOTE ("alenze")

One way to do this (sorry, lfmorrison's signed remainder isn't always mathematically correct - "we should round anything from 0.0 up to 0.49999999... as 0, and anything from 0.500000000...01 up to 0.9999999999999999... as 1":

CODE

; Division by 10, useing reciprocal multiplication
;
; Call with:
; 8 bit dividend in r16
;
; Returns:
; Result in r16
; Remainder in r18

mov r18, r16 ; save original dividend
ldi r17,26 ; reciprocal, scaled *256, off a bit
mul r16,r17

; result of multiplication now in r1:r0
; use only r1, thereby effectively divide by 256
dec r1 ; if imprecise scaling value influences result,
; result will be '+1'. Decrement to avoid neg.
; value in later subtraction
ldi r17,10 ; re-use r17 for divisor
mov r16,r1 ; save result/256
mul r16,r17 ; find remainder by multiplication of result by 10d

; result again in r1:r0
; get remainder and correct result of 'by 10'
sub r18,r0
cpi r18,10
brlo done
subi r18,10
inc r16

done:
; result in r16, remainder in r18

;optional rounding:
cpi r18,5
brlo done_r
inc r16
done_r:

QUOTE ("lfmorrison")

Frankly, I don't buy that "negative remainder isn't correct" argument.

It's a non-standard representation. So are improper fractions. But just like improper fractions, the result is numerically dead-on.

AFAIC, 25 divided by 4 can be perfectly legally expressed as 6 remainder 1. And that is exactly identical to 5 remainder 5, or 7 remainder -3.

The only possible result from RetroDan's expression would still be guaranteed to be within 1 LSB of the true result. And the "traditional approach" cannot offer any better than getting within 1 LSB either.

But if it really bothers you, then you could always test the sign bit of the remainder... if it is set, then subtract 1 from the quotient and add 10 to the remainder.

CODE

DIV10: LDI B,51
MUL A,B
INC R1 ;R1=A/5
LSR R1 ;R1=(A/5)/2 = A/10
; Luke's insertion
MOV C, R1
LDI B, 10
MUL C, B
SUB A, R0
; 'A' contains the (signed) remainder.
; sign of the remainder indicates whether it is an:
; - under-estimate (positive remainder), or
; - over-esitmate (negative remainder)
; 'C' contains the quotient
; We can return here with a totally valid and numerically correct result.
; But for the sticklers among us, let's convert it
; to a "cannonical form".
SBRS A, 7; test the sign of result.
RJMP PositiveRemainder
; We have a negative remainder; subtract 1 from
; the quotient and add 10 to the remainder.
DEC C
ADD A, B
PositiveRemainder
; The result is now in perfect "cannonical" form.
RET

QUOTE ("lfmorrison")

And given the limited range of values we're concerned with here, that result (after a single check of the sign on the remainder, and possibly a single subtraction of 1 / addition of 10) will be in the "cannonical" form. (Ie. a guaranteed underesitmate in the result, and a remainder that is guaranteed to be positive, and bound between 0 and 9.)

QUOTE ("lfmorrison")

Frankly, I don't buy that "negative remainder isn't correct" argument

QUOTE ("alenze")

You are right and I phrased it badly: of course the signed remainder is correctly calculated (cleaner than in my example, too - 3 or four cycles saved).

It's the 'inbuild rounding' whose threshold is off by one, mathematically speaking ( ):

The quotient 'n.5' (6.5 for example if dviding 65/10) should already be rounded up to n+1 ('7'), here it is still left at '6'.
66/10 (6.6) is correctly rounded to '7' as 64/10 (6.4) becomes a rounded '6'. It's just the '.5' rounding which doesn't quite work (aren't those mathematicians a fascinating breed?).

Thank you all for the wonderful feed-back. The information was invaluable and probably saved me a lot of head-scratching as you'll soon find out.

I was pleased-as-punch that my "quirky" little division by 10 routine worked. I was even more delighted to find out that it did a pretty good job of rounding to boot. However, when I got around to using it for my original purpose, I realized that rounding was the last thing I wanted.

The original use for the routine was to break-down an unsigned single byte for display on the Butterfly LCD. Well I was getting results like: 74, 75, 76, 77, 80, 80, 80, 81, 82, 83. Obviously the little DIV10 routine was working over-time and rounding, so a few fine adjustments were needed to "UN-ROUND" the results.

I know that you guys have already worked out your own versions, here is mine:

CODE

;-----------------------------------;
; RETRO (SYNTHETIC) DIVISION BY 10 ;
; ANSWER IN R1, R0=REM, A:PRESERVED;
;-----------------------------------;
DIV10: PUSH B
LDI B,26 ;MUL BY 26
MUL A,B ;R1=A/10
PUSH R1 ;BRUTE-FORCE CALC OF REMAINDER
LDI B,10 ;CALC REM
MUL R1,B ;R0=10xR1(QUOT)
POP R1 ;RESTORE QUOT
SUB R0,A ;SUBTRACT REMx10
NODJST: NEG R0 ;MAKE POSITIVE
BRPL NONEG;STILL NEG?
ADD R0,B ;OOPS MAKE
DEC R1 ;ADJUSTMENTS
NONEG: RET

If you're wondering why I calculate the remainder "backwards" then negate it, it's to preserve the value of A. If there's no need to preserve A then the remainder could be calculated the other-way-around and eliminate the need for the NEG R0 line. Other than removing that one statement I don't know if it can be optimized any further, but it sure would be nice.

Hello,

I really appreciate your work on this, however there is a problem with the routines - the calculations simply do NOT work well! The idea of multiplying by fraction (26/256) instead of deviding by 10 is very smart, but the error is too big. I re-checked all the calculations and here are my results:

X = A / 10

1) X = (A +1) * 51 / 512
=>represents pre-incrementation, multiplication by 51, throwing away the lower byte (r0) and shifting right once
-- this one is the best. Gives accurate results up to number 260 which is faulty (returns 25). It doesn't matter if we are using only 8-bit numbers for the input.
-- care needs to be taken if A is 255
-- error: (510/512) : (1/10) = -0.3906% (thus A needs to be pre-incremented)

2) X = A * 26 / 256
=> represents multiplication by 26 and throwing away the lower byte (r0)
-- this one is quite useless, gives accurate results up to number 69 (returns 7)
-- error: (26/256) : (1/10) = +1.5625% (this is 4 biger than in the first case)

Yours Lomm :)

Thanks for the feed-back Lomm:

QUOTE

2) X = A * 26 / 256
=> represents multiplication by 26 and throwing away the lower byte (r0)
-- this one is quite useless, gives accurate results up to number 69 (returns 7)

Lomm, 69/10 = 7 is correct if you are rounding.

Did you read the entire thread? There is discussion about this "rounding" and added code that would "un-round" so I could use it in a Butterfly LCD driver routine where I needed it to "truncate" 69/10 = 6 instead of rounding up to 7.

Hi,

After reading the thread I made an own version with following function:

Input: unsigned Byte value in r24
Output: three digits in r22(MSB), r21 and r20 (LSB)

CODE

ldi r16, 205 ; value * 205 / (256 * 8) gives result in r1
ldi r17, 10 ;
mul r24, r16
rcall Sh3R1_0 ; divide by 8 = 3 right shifts
mov r21, r1 ; save result and work with remainder
mul r0, r17 ; remainder * 10 gives remainder in r1
mov r20, r1 ; One-Digit ready
mul r21, r16 ; calculate ten- and hundred-digit
rcall Sh3R1_0
mov r22, r1 ; hundred-digit ready
mul r0, r17 ; calculate ten-digit from remainder
mov r21, r1 ; ten-digit to output-register
ret

Sh3R1_0:
lsr r1 ; divide by 8
ror r0
lsr r1
ror r0
lsr r1
ror r0
inc r0 ; adjust remainder for correct result in
; all situations (rounding problem)
ret

regards Josef

Hey Josef,

the mul by 205 is verry nifty for bcd!

if you just need div10 then the following code is the right thing.

CODE

div10:
ldi temp1, 205
mul temp1, input
lsr R1
lsr R1
lsr R1
mov result, R1
ret