Author Topic: 24 bit division  (Read 8829 times)

0 Members and 1 Guest are viewing this topic.

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
24 bit division
« 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...

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: 24 bit division
« 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.
« Last Edit: February 16, 2011, 03:44:11 pm by thepenguin77 »
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit division
« 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?

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55942
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: 24 bit division
« 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. :)

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit division
« 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!
« Last Edit: February 17, 2011, 03:26:46 am by cerzus69 »

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: 24 bit division
« 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
« Last Edit: February 17, 2011, 04:36:38 am by Runer112 »

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: 24 bit division
« 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. :)

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: 24 bit division
« Reply #7 on: February 16, 2011, 07:17:37 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.
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.
« Last Edit: February 16, 2011, 07:24:19 pm by thepenguin77 »
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit division
« 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 :)
« Last Edit: February 17, 2011, 04:26:30 am by cerzus69 »

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: 24 bit division
« 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.
« Last Edit: February 17, 2011, 03:58:31 am by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit division
« 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? ???

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: 24 bit division
« 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.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: 24 bit division
« 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
« Last Edit: February 18, 2011, 01:01:50 am by Runer112 »

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit division
« 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?

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit division
« 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.
« Last Edit: February 17, 2011, 04:51:35 am by cerzus69 »