Page 1 of 1

Division

Posted: Thu 06 Nov, 2008 11:24 pm
by King Harold
From the person you least it expected it from - me.

I give you, teh codez.

Code: Select all

div_h_l:	;returns e = h/l
		;c if error, nc if OK
		;kills af, e, hl
		;A/B (just names, will be used in comments)
	ld a,l
	or a
	ccf
	ret z	;return C if dividing by 0
	ld a,h
	cp l
	jr nc,{+}
	;divisor > dividend, return 0 but no error
	xor a
	ld e,a
	ret
+:	;all normal, divide
	ld h,1	;index, that's a one, a bit hard to see in this font
	;there is only 1 one in this code, namely this one.
	;MSbit line-up
-:	cp l  ;that's an L
	jr c,_shiftdone_goback
	bit 7,l
	jr nz,_shiftdone
	;shift
	add hl,hl	;L+L can never carry
	jr {-}
_shiftdone_goback:
	srl l
	srl h
_shiftdone:
	sub l
	ld e,h		;result = 0 + index
	ld d,a
-:	ld a,h
	or a
	ret z
	rra	;index >> 1
	ld h,a
	srl l	;B >> 1
	;if A>=B
	ld a,d
	cp l
	jr c,{-} ;A<B
	sub l
	ld d,a
	ld a,e
	add a,h
	ld e,a
	jr {-}
Whether this monster is actually any good (speed-wise) I don't know (someone analyse it, please?). What I do know, is that it gives the correct result.
What I also know, is that for 128bit numbers, this way is on average 10 times as fast as the usual restoring division. Which says nothing about 8bit number but at least it has a chance.
Also, I'm kinda braindead at the moment (had a test today + it's half past midnight) so there may be terrible mistakes/bugs/inefficiencies.. :oops:


Edit:

I also made a 16bit version.. well, I tried to. It doesn't really work..
Could someone have a look at it?

Code: Select all

div_hl_de:	;returns hl = hl / de
		;c if error
	ld a,d
	or e
	ccf
	ret z
	
	ld a,d
	cp h
	jr c,{+}
	ld a,e
	cp l
	jr c,{+}
	ld hl,0
	ret
+:	;MSbit line-up
	ld bc,1
	
-:	ld a,h
	cp d
	jr c,_goback
	ld a,l
	cp e
	jr c,_goback
	bit 7,h
	jr nz,_continue
	sla c
	rl b
	sla e
	rl d
	jr {-}
_goback:
	srl d
	rr e
	srl b
	rr c
_continue:
	or a
	sbc hl,de
	;hl = A
	;de = B
	;bc = index
	
	push hl
	ld h,b
	ld l,c		;hl = result, stacktop = A
	
-:	ld a,b
	or c
	jr nz,{+}
	pop de
	ret
+:	srl d
	rr e
	srl b
	rr c
	ex (sp),hl  ;I don't see this one a lot - maybe it's proof of how braindead I am..
	;hl = A, stacktop = result
	or a
	sbc hl,de
	jr c,_wassmaller
	ex (sp),hl
	add hl,bc
	jr {-}
_wassmaller:
	adc hl,de
	ex (sp),hl
	jr {-}

Re: Division

Posted: Fri 07 Nov, 2008 3:36 am
by calc84maniac
I don't think that monster can really compare to *cough*

Re: Division

Posted: Fri 07 Nov, 2008 5:49 am
by Dwedit
I just used a stolen disassembly of the TI-83 ROM's _divhlbya for any calc that didn't define that routine (*cough* TI-85)

Re: Division

Posted: Fri 07 Nov, 2008 12:04 pm
by benryves
Have you benchmarked your routine against other implementations, such as those on Z80 bits?
calc84maniac wrote:I don't think that monster can really compare to *cough*
There's an up to date version on baze's site.

Re: Division

Posted: Fri 07 Nov, 2008 12:31 pm
by King Harold
Benchmark: the 8bit version is "a bit" faster on average (as in: about 10%) and it's the average over all 64k inputs
possibly because it cheats and tests whether the divisor is greater than the dividend though

Analysed it a bit: the speed depends mostly on the result. The smaller the result, the faster it runs. 255/1 is very slow, 64/64 is done in no time.