a few quick optimizations I see are changing those Inc/dec ix to use ixl instead

Sure! Didn't see that one. The problem there is also that those are undocumented and don't run on some emulators.

you don't need the `or a` before the sbc

Yes, that's also right. Wasn't too smart of me. But hey, at least I wrote a 32 div 16 routine, okay?

Do you prefer speed optimizations or size optimizations, btw?

Usually, I prefer speed, but it shouldn't be to big either. When the program is done and it runs too slowly or is too big, I can optimize as I need.

The resulting routine would look like this:
div32_16:
 ld de,0 ; 10
 ld a,32 ; 7
div32_16loop:
 add ix,ix ; 15
 adc hl,hl ; 15
 ex de,hl ; 4
 adc hl,hl ; 15
 sbc hl,bc ; 15
 inc ixl ; 8
 jr nc,cansub ; 12/7
  add hl,bc ; 11
  dec ixl ; 8
cansub:
 ex de,hl ; 4
 dec a ; 4
 jr nz,div32_16loop ; 12/7
 ret ; 10
This takes between 3838 and 3390 T-States, which is .64 to .57 ms.

I also though that maybe we could invert BC so then we can use ADD HL,BC instead of SBC, which is 4 T-States faster, but this has the problem that we would need SBC further on. This would bring down the best case scenario time, but up the worst case.

About the square root routine: is it still needed? I already know how the sqrt algorithm works. I just have to implement it, but I don't have the time now.

EDIT: maybe we could put this on http://z80-heaven.wikidot.com/math, where many other math routines already reside?

I am making a double-post because this post is very distinct from the other.
Before I proceed, the routine doesn't take into account that the `adc hl,hl` could overflow on the 17th iteration and beyond if BC>32768. For example, 0x80000000/0x8001 will leave HL as 8000h on the 16th iteration, and then 0x0000 on the 17th.

Before we fix that, notice that you are using two `ex de,hl` each iteration, but here is a more efficient way:
div32_16:
 ex de,hl   ; 4
 ld hl,0    ; 10
 ld a,32    ; 7
div32_16loop:
 add ix,ix  ; 15
 rl e       ; 8
 rl d       ; 8
 adc hl,hl  ; 15
 sbc hl,bc  ; 15
 inc ixl    ; 8
 jr nc,cansub  ; 12/7
  add hl,bc ; 11
  dec ixl   ; 8
cansub:
 dec a      ; 4
 jr nz,div32_16loop ; 12/7
 ex de,hl   ; 4
 ret        ; 10
This ends up adding 2 bytes and 8cc to the overhead code, but saves 7cc per iteration, for a net savings of 216cc.

But we can replace those `rl e` with `rla`, we'll save 4cc per iteration.
div32_16:
 ex de,hl   ; 4
 ld hl,0    ; 10
 ld a,e     ; 4
 ld e,32    ; 7
div32_16loop:
 add ix,ix  ; 15
 rla        ; 4
 rl d       ; 8
 adc hl,hl  ; 15
 sbc hl,bc  ; 15
 inc ixl    ; 8
 jr nc,cansub  ; 12/7
  add hl,bc ; 11
  dec ixl   ; 8
cansub:
 dec e      ; 4
 jr nz,div32_16loop ; 12/7
 ex de,hl   ; 4
 ret        ; 10
This is actually a cheap optimization. It adds no extra bytes, but adds 4cc to overhead and saves 4cc per iteration, for a net savings of 124cc!

But in a similar vein, we can just split up the code into 4 parts with a common subroutine, reducing the shifting work:
div32_16:
;136+4*div32_16_sub8
;min: 2180cc
;max: 2788cc
;avg: 2484cc
;49 bytes
  ex de,hl   ; 4
  ld hl,0    ; 10

  ld a,d              ; 4
  call div32_16_sub8  ; 17
  ld d,a              ; 4

  ld a,e              ; 4
  call div32_16_sub8  ; 17
  ld e,a              ; 4

  ld a,ixh            ; 8
  call div32_16_sub8  ; 17
  ld ixh,a            ; 8

  ld a,ixl            ; 8
  call div32_16_sub8  ; 17
  ld ixl,a            ; 8

  ex de,hl   ; 4
  ret        ; 10

div32_16_sub8:
;119+8*div32_16_sub
;min: 511cc
;max: 663cc
;avg: 587cc
  call +_
_:
;17+2(17+2(div32_16_sub)))
  call +_
_:
;17+2(div32_16_sub)
  call div32_16_sub
div32_16_sub:
;min: 49cc
;max: 68cc
;avg: 58.5cc
 add a,a    ; 4
 adc hl,hl  ; 15
 sbc hl,bc  ; 15
 inc a      ; 4
 ret nc     ;11/5
 add hl,bc  ; 11
 dec a      ; 4
 ret        ; 10


---

The above routine works when BC<=0x8000, but to extend it, we'll need to take care of the overflow and that will slow it down:
div32_16:
;136+4*div32_16_sub8
;min: 2340cc
;max: 3012cc
;avg: 2676cc
;55 bytes
  ex de,hl   ; 4
  ld hl,0    ; 10

  ld a,d              ; 4
  call div32_16_sub8  ; 17
  ld d,a              ; 4

  ld a,e              ; 4
  call div32_16_sub8  ; 17
  ld e,a              ; 4

  ld a,ixh            ; 8
  call div32_16_sub8  ; 17
  ld ixh,a            ; 8

  ld a,ixl            ; 8
  call div32_16_sub8  ; 17
  ld ixl,a            ; 8

  ex de,hl   ; 4
  ret        ; 10

div32_16_sub8:
;119+8*div32_16_sub
;min: 551cc
;max: 719cc
;avg: 635cc
  call +_
_:
;17+2(17+2(div32_16_sub)))
  call +_
_:
;17+2(div32_16_sub)
  call div32_16_sub
div32_16_sub:
;54+{0,2+{0,19}}
;min: 54cc
;max: 75cc
;avg: 64.5cc
  add a,a    ; 4
  inc a      ; 4
  adc hl,hl  ; 15
  jr c,+_    ;12/7
  sbc hl,bc  ; 15
  ret nc     ;11/5
  add hl,bc  ; 11
  dec a      ; 4
  ret        ; 10
_:
  or a       ; 4
  sbc hl,bc  ; 15
  ret        ; 10
This adds 6 bytes, and 192cc on average, so it's not too bad.

---

Now we move in with your idea to negate BC upon entry to improve some cases. That allows some other optimizations too, like not needing to reset the carry flag in the last case of div32_16_sub:
div32_16:
;HLIX/BC -> HLIX remainder DE
;158+4*div32_16_sub8
;min: 2298cc
;max: 3034cc
;avg: 2546cc
;59 bytes
  ex de,hl   ; 4

; Negate BC to allow add instead of sbc
  xor a      ; 4
; Need to set HL to 0 anyways, so save 2cc and a byte
  ld h,a     ; 4
  ld l,a     ; 4
  sub c      ; 4
  ld c,a     ; 4
  sbc a,a    ; 4
  sub b      ; 4
  ld b,a     ; 4


  ld a,d              ; 4
  call div32_16_sub8  ; 17
  ld d,a              ; 4

  ld a,e              ; 4
  call div32_16_sub8  ; 17
  ld e,a              ; 4

  ld a,ixh            ; 8
  call div32_16_sub8  ; 17
  ld ixh,a            ; 8

  ld a,ixl            ; 8
  call div32_16_sub8  ; 17
  ld ixl,a            ; 8

  ex de,hl   ; 4
  ret        ; 10

div32_16_sub8:
;119+8*div32_16_sub
;min: 535cc
;max: 719cc
;avg: 597cc
  call +_
_:
;17+2(17+2(div32_16_sub)))
  call +_
_:
;17+2(div32_16_sub)
  call div32_16_sub
div32_16_sub:
52+{4,0+{0,23}}
;min: 52cc
;max: 75cc
;avg: 59.75cc
  add a,a    ; 4
  inc a      ; 4
  adc hl,hl  ; 15
  jr c,+_    ;12/7
  add hl,bc  ; 11
  ret c      ;11/5
  sbc hl,bc  ; 15
  dec a      ; 4
  ret        ; 10
_:
  add hl,bc  ; 11
  ret        ; 10
This adds a net of 4 bytes. It adds 22cc to the worst case, saves 42cc in the best case, but manages to bring the average case down by 130cc!

But now let's take advantage of the output flags in the sub routine. It turns out that except for that last case, the output is carry flag reset if the bit shifted in should be 0, and carry set if the bit should be 1.
div32_16:
;HLIX/BC -> HLIX remainder DE
;174+4*div32_16_sub8
;min: 2186cc
;max: 2794cc
;avg: 2466cc
;61 bytes
  ex de,hl   ; 4

; Negate BC to allow add instead of sbc
  xor a      ; 4
; Need to set HL to 0 anyways, so save 2cc and a byte
  ld h,a     ; 4
  ld l,a     ; 4
  sub c      ; 4
  ld c,a     ; 4
  sbc a,a    ; 4
  sub b      ; 4
  ld b,a     ; 4


  ld a,d              ; 4
  call div32_16_sub8  ; 17
  rla                 ; 4
  ld d,a              ; 4

  ld a,e              ; 4
  call div32_16_sub8  ; 17
  rla                 ; 4
  ld e,a              ; 4

  ld a,ixh            ; 8
  call div32_16_sub8  ; 17
  rla                 ; 4
  ld ixh,a            ; 8

  ld a,ixl            ; 8
  call div32_16_sub8  ; 17
  rla                 ; 4
  ld ixl,a            ; 8

  ex de,hl   ; 4
  ret        ; 10

div32_16_sub8:
;119+8*div32_16_sub
;min: 503cc
;max: 655cc
;avg: 573cc
  call +_
_:
;17+2(17+2(div32_16_sub)))
  call +_
_:
;17+2(div32_16_sub)
  call div32_16_sub
div32_16_sub:
;48+{8,0+{0,19}}
;min: 48cc
;max: 67cc
;avg: 56.75cc
  rla        ; 4
  adc hl,hl  ; 15
  jr c,+_    ;12/7
  add hl,bc  ; 11
  ret c      ;11/5
  sbc hl,bc  ; 15
  ret        ; 10
_:
  add hl,bc  ; 11
  scf        ; 4
  ret        ; 10
This costs two extra bytes, but saves 112cc in the best case, 240cc in the worst case, and 80cc on average !

I wonder, if you can make my routine twice as fast and if you've written complete support for floats, why didn't you write this routine in the first place?

It was just because my float routines were special-purpose and writing a general-purpose routine was a daunting idea (which is why I'm grateful for your work). For the float routines, I can always guarantee the top 16 bits are smaller than BC, resulting in a routine that is under 900cc. That said, I should update my above routine with a trick I came up with for those (it reduces the problem so that BC is always less than 32768, )(correctly) correcting later so that there is no overflow to check for).

Also, I was having trouble with getting INC/DEC IXL to work for some reason. Haven't had the time to investigate that though. It could be that I just typed in the wrong opcode because I have a bad assembler which doesn't support it apparently and it's too much of a hassle to get a new one on Linux.

I use SPASM-ng and that has been great for me.

As for your optimizations, I could follow along until you got those subroutines in. (EDIT: I think I got it now) And that might also be a problem if you have limited stack space or if you can't use the stack at all (in which case the routine would be inline). I tend to put RAM page 02 into bank C and completely fill it up with data, not leaving any place for a stack.

Hmm, I'll keep this in mind if I work more on these.

Another, easy way of doing this would be by thinking of the 32 and 16 bit numbers as 4&2-digit base-256 numbers and using a routine for smaller numbers to do the actual division.

I do this in the extended-precision float routines, and it requires two multiplications (one multiply if you don't need the remainder), but could come out faster. I might pursue this, too. In my float routines, because they were special-purpose, this method didn't pay off until the 32/32 divisions and up. However, general-purpose 32/16 might benefit.

[quote author=fghsgh link=topic=18691.msg406921#msg406921 date=1552874767]
My trick: pen & paper & sleep
[/quote]
Hey, that's the trick I use! I should clarify: without motivation, I am lazy.

[quote author=fghsgh link=topic=18691.msg406921#msg406921 date=1552874767]
This is not the first time someone has recommended SPASM to me. It is, however, the first time someone provided me with a Github link and I thought it was only available for Windows until now. It would also mean that I have to transform all my previous programs (or at least include files) to this syntax.
Glad I could help! I think with spasm you can do such things as #define TASM or something like that and it'll allow `equ` instead of `=` and whatnot.

I don't think that's too hard in this case: just djnz 8 times

True (except not using djnz since that would use B !), but you would have to call that routine which uses a stack anyways I imagine you mean a very limited stack as opposed to no stack whatsoever?

I will try to make the sqrt routine asap, if I don't forget. It'll probably be for next weekend.

Good luck! The pseudocode outlined here has yielded me better results than algorithm I learned as a kid. It's the same algorithm, just structured better for programming instead of computing by hand.

True (except not using djnz since that would use B !), but you would have to call that routine which uses a stack anyways I imagine you mean a very limited stack as opposed to no stack whatsoever?

About not using B: I thought that was evident so I left it out.
I meant copy & pasting the routine into the program, where it is needed:
; code code code
; set arguments for divisionn
; insert division routine here
; code code code
... or I would have to put page 0 back in before calling.

It's not that I often need division, especially not in a stackless environment, but it's handy to have either way.

I haven't had much luck with this one, unfortunately. If you are open to using more stack space or external memory, you can take advantage of first working with 8-bit values, then 16-bit, then 32-bit.

Oh! I was just about to post and you posted. That looks like a much cleaner routine!

EDIT: One thing though: In you routine, A is 0 until the last iteration, so you can make the last iteration a special case and speed up the inner loop.

The remainder is no more than 2sqrt(x), so in this case at most 0x1FFFE, but on the 15th iteration it is at most 0xFFFE

Well,why not just do ex de,hl first and make the first 8 iterations add hl,hl and then another ex de,hl and the final iterations add hl,de.

In the version I'm working on, I have 3 groups of 4 iterations (shifting 1 byte) and then three iterations and then 1 special case. Something is wrong with it though, so I have to work more on it.