[z80] Fastest long-division?

Got questions? Got answers? Go here for both.

Moderator: MaxCoderz Staff

Post Reply
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

[z80] Fastest long-division?

Post by King Harold »

I want to divide x<<128 by y.
Of course, a full 256-by-128-bit division is not required, because the lower half of x<<128 is zero anyway (so we might as well start out with "remainder = x, result = 0")
The code for that is this disaster:

Code: Select all

longdiv:
	; divides big endian int128 at hl * 1<<128 by big endian int128 at de
	; result at $8000 (big endian)
	; returns with Carry = true if the result overflows (result must then hold x<<127 / y)
	; returns with Carry = false otherwise (result must hold x<<128 / y)
	.define _result $8000
	.define _divisor $8020
	push de
	; copy dividend into upper half of result (odd but correct since the lower half is 0)
	ld de,_result
	ld bc,16
	ldir
	; copy divisor 
	pop hl
	ld de,_divisor 
	ld bc,16
	ldir
	; zero lower half of result
	ld hl,_result+16
	ld (hl),0
	ld de,_result+17
	ld bc,15
	ldir
	; actual division
	ld c,129
	;reset carry because on the first iteration 
	;there hasn't been a leftshift yet that could carry
	;so we must check whether the high half of the result is smaller than the divisor
	or a
	;also make hl point to _result because we skip the first leftshift
	ld hl,_result-1
	jr _entrance
_divloop:
	; shift result left
	ld hl,_result+31
	ld b,l	;b = 31
	; optimized first iteration
	sla (hl)
-:	dec hl
	rl (hl)
	djnz {-}
	dec hl
	; entrance here to skip first leftshift
_entrance:
	; if the left shift overflowed, the high half of the result
	; is definitely NOT smaller than the divisor, so skip the comparison
	jr c,_dosubtract
	; hl -> _result-1
	ld de,_divisor-1
	ld b,16
-:	inc hl
	inc de
	ld a,(de)
	cp (hl)
	jr z,{+}
	jr nc,_skipsubtract	; (result >> 128) > divisor 
	jr _dosubtract	; (result >> 128) < divisor 
	; loop while equal
+:	djnz {-}
	; if equal, no need to subtract
	jr _skipsubtract
_dosubtract:
	; increment result
	; it was leftshifted so it can't carry
	ld hl,_result+31
	inc (hl)
	; subtract divisor from upper half of result
	ld de,_result+15
	ld hl,_divisor+15
	ld b,e	; b = 15
	
	ld a,(de)
	sub (hl)
	ld (de),a
	
-:	dec de
	dec hl
	ld a,(de)
	sbc a,(hl)
	ld (de),a
	djnz {-}
_skipsubtract:
	dec c
	jr z,_exit
	ld a,(_result+16)
	rla
	jr nc,_divloop
	ret
_exit:
	or a
	ret
As far as I know, it gives the correct result.
But I think there should be faster ways to do this - are there any? Or does it have to be this algorithm, but more optimized?
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: [z80] Fastest long-division?

Post by benryves »

I wish I could help, but I doubt my solution would be any better than yours, sorry. :-(
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [z80] Fastest long-division?

Post by King Harold »

Ok I guess I'll just keep using this code
Post Reply