Author Topic: 24 bit division (Read 9507 times)

cerzus69 · « **on:** February 16, 2011, 08:51:38 am »

Hey, I've been looking around for 2 days now how to do 24 by 24 bit division in z80 asm. I've found 16/8, 16/16, 24/8, 24/16 and even 32/8. I'm sure there must be a 24/24 out there, but I can't find it. Does anyone know how to do this? I'm getting quite desperate...

thepenguin77 · « **Reply #1 on:** February 16, 2011, 03:37:27 pm »

I don't know of any so I just made this up.

Code: [Select]


;###################################
;div 24 by 24
;bcd / ehl
;ouput: ehl = quotient
;	bcd = remainder

divScratch	equ	$8000

divBCDbyEHL:
	ld	ix, divScratch
	ld	(ix), d
	ld	(ix+1), c
	ld	(ix+2), b
	xor	a
	ld	(ix+3), a
	ld	(ix+4), a
	ld	(ix+5), a

	ld	b, 24
div24Loop:
	sla	(ix)
	rl	(ix+1)
	rl	(ix+2)
	rl	(ix+3)
	rl	(ix+4)
	rl	(ix+5)

	ld	a, (ix+5)
	cp	e
	jr	c, notBigEnough
	jr	nz, oversize
	
	ld	a, (ix+4)
	cp	h
	jr	c, notBigEnough
	jr	nz, oversize

	ld	a, (ix+3)
	cp	l
	jr	c, notBigEnough
oversize:
	inc	(ix)
	ld	a, (ix+3)
	sub	l
	ld	(ix+3), a
	ld	a, (ix+4)
	sbc	a, h
	ld	(ix+4), a
	ld	a, (ix+5)
	sbc	a, e
	ld	(ix+5), a
	

notBigEnough:
	djnz	div24Loop

	ld	l, (ix)
	ld	h, (ix+1)
	ld	e, (ix+2)
	ld	d, (ix+3)
	ld	c, (ix+4)
	ld	b, (ix+5)
	ret

As far as I know, it works. You can change the outputs and inputs pretty easily as you can see, and you'll have to define divScratch to somewhere.

But, if I know this forum, just wait a few hours and you'll have one half as big and twice as fast from calc84maniac.

Edit:
Oops, that version had values hardcoded in, now it doesn't.

cerzus69 · « **Reply #2 on:** February 16, 2011, 05:16:09 pm »

Woah! How did you come up with that that fast? Thanks a lot! I actually found a way to get around the 24 bit division. Since the quotient in my specific case would always fit in one byte (I am scaling the ratio between two 24-bit values from 0 to 50), I can just omit the lsb of the dividend and the divisor and the result will still be sufficiently precise.

I will only use the two msbs of both values. If they are below 65536, I can just use the two lowest bytes, otherwise I use the two highest bytes. I multiply the lowest value with 50 (so that ends up being a 24-bit integer again) and then I divide them with a 24/16 division routine. Does the job!

Still, I am amazed at how easily you came up with this routine (I should have paid more attention at school when they were explaining long division) and I will put it in my math libary if that's okay with you. What's at $8000, though? Beause you are overwriting the 6 bytes in memory there aren't you?

DJ Omnimaga · « **Reply #3 on:** February 16, 2011, 05:28:14 pm »

Yeah some people here amazes me sometimes. By the way how large is this Thepenguin77?

Also welcome here Cerzus69.

cerzus69 · « **Reply #4 on:** February 16, 2011, 06:08:03 pm »

Thank you, DJ_O! I like this place already.

I think that it is about 110 bytes. A little on the large side, especially because of the all the ld (ix), but I can't come up with a better one myself and it's the first one in z80 asm that I've seen. Thanks again, thepenguin77!

Runer112 · « **Reply #5 on:** February 16, 2011, 06:48:28 pm »

I haven't tested it myself, but try this? It appears to me that it should work, and it doesn't require any scratch memory. And by my count, it's only 43 bytes.

Code: [Select]

Div24by24:
	ld	b,a			;INPUTS:	ahl = dividend	cde = divisor
	push	hl			;OUTPUTS:	cde = quotient	ahl = remainder
	pop	ix
	ld	l,24
	push	hl
	xor	a
	ld	h,a
	ld	l,a
__Div24by24loop:
	add	ix,ix
	rl	b
	adc	hl,hl
	rla
	cp	c
	jr	c,__Div24by24skip
	jr	nz,__Div24by24setbit
	sbc	hl,de
	add	hl,de
	jr	c,__Div24by24skip
__Div24by24setbit:
	sbc	hl,de
	sbc	a,c
	inc	ix
__Div24by24skip:
	ex	(sp),hl
	dec	l
	ex	(sp),hl
	jr	nz,__Div24by24loop
	pop	de
	ld	c,b
	push	ix
	pop	de
	ret

ztrumpet · « **Reply #6 on:** February 16, 2011, 06:49:16 pm »

It looks like "appData" is at 8000h, so I doubt if there's anything important there.

Welcome to the forums, cerzus.

thepenguin77 · « **Reply #7 on:** February 16, 2011, 07:17:37 pm »

Quote from: thepenguin77 on February 16, 2011, 03:37:27 pm

But, if I know this forum, just wait a few hours and you'll have one half as big and twice as fast from ~~calc84maniac~~ Runer112.

Quote from: Runer112 on February 16, 2011, 06:48:28 pm

I haven't tested it myself, but try this? It appears to me that it should work, and it doesn't require any scratch memory. And by my count, it's only 43 bytes.

Meh, you win.

Edit:
$8000 - ~$8180 is free to do whatever with. Just don't count on it being preserved if you use bcalls.

cerzus69 · « **Reply #8 on:** February 17, 2011, 03:47:34 am »

Thank you, Ztrumpet, glad to be here

I will test both routines now. I doubt anyone will halve the memory footprint again, so if it works I think will use Runer's... But... Now that I think of it, maybe you've read that I managed to drop off a byte of precision so that it turned out to be only two 16-bit values I am working on. I multiply the smaller of those by 50 so I get this scale, which is going to be a progress bar of 50 pixels high that you have to fill on each level: 50 * current score(2 msbs of the real value) / score needed(also just the 2 msbs). I multiply the 2 msbs of the current score by 50 first (the result will be in 24 bits again) and then divide by the score needed. Obviously this is now only a 24/16 division.
So now that I see that you've come up with 24/24 (still don't know how both of you did that), I could leave the lsbs in, but I still have to multiply by 50 first. I know for a fact that in my case that the current score times 50 would not exceed the 16843007 (correct me if I'm wrong) max value of 24-bit. What I'm saying here is that I would need a 24by8 multiply function as well, before I can divide 24/24. Anyone up to the challenge?

EDIT: I just tested both Runer112's and thepenguin77's routines and they both seem to work fine. I don't really know what would be good test values... I tried to divide 0 by 0 and they both give 16777215 as the answer, but I guess since they both do, it's okay

AngelFish · « **Reply #9 on:** February 17, 2011, 03:56:22 am »

I don't know how to write the exact z80 hex, but here's a simple algorithm to divide n bit numbers by m bit numbers:

Shift m once to the right. Keep doing this until m is a reasonable size, probably 4 bits.

Take the highest nibble of the numerator N and compare it to the denominator M. If the byte of N (N') is greater than or equal to the reduced M (M'), output 1 and subtract M' from N'. If N' is less than M', output 0.

Shift N one bit to the left and repeat.

Keep going until you run out of bits in N.

Then right shift the answer as many times as you originally right shifted M. This is your answer.

You admittedly lose some precision with this technique for larger numbers, but it should be fine for most applications and prevents messy division with multiple large numbers.

cerzus69 · « **Reply #10 on:** February 17, 2011, 04:22:28 am »

Qwerty.55: I am trying to understand your algorithm, but you seem to be talking about the highest nibble of N and then about the byte, which one is it? Also, how you would you determine what is a 'reasonable size' for M in the beginning?

AngelFish · « **Reply #11 on:** February 17, 2011, 04:27:37 am »

Er, I meant nibble. The byte thing was something I forgot to edit out. And reasonable size is just defined as whatever is easiest to work with. If that's bytes, then go ahead and use them.

Runer112 · « **Reply #12 on:** February 17, 2011, 04:35:33 am »

You're multiplying just the 2 most significant bytes of the score, right? May I suggest the following then:

Code: [Select]

Mul16by8:
	ex	de,hl			;INPUTS:	hl = multiplicand	a = multiplier
	ld	hl,0			;OUTPUTS:	ahl = product	b = 0
	ld	b,8
__Mul16by8loop:
	add	hl,hl
	rla
	jr	nc,__Mul16by8skip
	add	hl,de
	adc	a,0
__Mul16by8skip:
	djnz	__Mul16by8loop
	ret

And if you only need a 24/16 division routine, this should hopefully work:

Code: [Select]

Div24by16:
	push	hl			;INPUTS:	ahl = dividend	de = divisor
	pop	ix			;OUTPUTS:	ahl = quotient	de = divisor
	ld	hl,0
	ld	b,24
__Div24by16loop:
	add	ix,ix
	rla
	adc	hl,hl
	jr	c,__Div24by16setbit
	or	a
	sbc	hl,de
	add	hl,de
	jr	c,__Div24by16skip
__Div24by16setbit:
	or	a
	sbc	hl,de
	inc	ix
__Div24by16skip:
	djnz	__Div24by24loop
	push	ix
	pop	hl
	ret

cerzus69 · « **Reply #13 on:** February 17, 2011, 04:38:36 am »

Ahh, okay, I get it. You just only keep the 4 (or 8, or X, depending more on precision than ease to work with I suppose) most significant bits of M and then shift N along that, right?

cerzus69 · « **Reply #14 on:** February 17, 2011, 04:48:14 am »

Yes, Runer112, you are right, but that is because I couldn't get a 24/24 division routine. I am actually using those two routines at the moment, although slightly different, from <a href="http://baze.au.com/misc/z80bits.html">here</a>.
Only using the two msbs isn't really a problem, but I'm a getting some slight rounding errors once in a while, so using all 3 bytes would be better I guess. But it's a matter of weighing perfect graphics against speed in this case, since I'm only using it to display the progress bar on screen.

EDIT: I might actually use your Mul16by8 routine instead of the one from that link, because of the size improvement. Or... I'll implement them both and use #define to choose which one you want.

Author Topic: 24 bit division (Read 9507 times)

cerzus69

24 bit division

thepenguin77

Re: 24 bit division

cerzus69

Re: 24 bit division

DJ Omnimaga

Re: 24 bit division

cerzus69

Re: 24 bit division

Runer112

Re: 24 bit division

ztrumpet

Re: 24 bit division

thepenguin77

Re: 24 bit division

cerzus69

Re: 24 bit division

AngelFish

Re: 24 bit division

cerzus69

Re: 24 bit division

AngelFish

Re: 24 bit division

Runer112

Re: 24 bit division

cerzus69

Re: 24 bit division

cerzus69

Re: 24 bit division