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

Division

Post 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 {-}
User avatar
calc84maniac
Regular Member
Posts: 112
Joined: Wed 18 Oct, 2006 7:34 pm
Location: The ex-planet Pluto
Contact:

Re: Division

Post by calc84maniac »

I don't think that monster can really compare to *cough*
~calc84maniac has spoken.

Projects:
F-Zero 83+
Project M (Super Mario for 83+)
User avatar
Dwedit
Maxcoderz Staff
Posts: 579
Joined: Wed 15 Dec, 2004 6:06 am
Location: Chicago!
Contact:

Re: Division

Post 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)
You know your hexadecimal output routine is broken when it displays the character 'G'.
User avatar
benryves
Maxcoderz Staff
Posts: 3080
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: Division

Post 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.
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: Division

Post 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.
Post Reply