Fastest Divide by 6

The place for codemasters or beginners to talk about programming any language for the Spectrum.
User avatar
RMartins
Manic Miner
Posts: 258
Joined: Thu Nov 16, 2017 3:26 pm

Fastest Divide by 6

Post by RMartins » Sun Dec 31, 2017 3:08 pm

In case of multiplication by 6, it's easy:

N*6 = N*2*3 == N*2*2 + N*2
which can be implemented with: 2 shifts + 1 Add, and a temp register. (Or 3 Adds and a temp register)

Code: Select all

; A * 6
ADD	A, A	; *2
LD	B, A	; Temp register for A*2
ADD	A, A	; *4
ADD	A, B	; *6
But division by 6 doesn't seem as easy.


NOTE: I can always loop unroll a generic division, for specific divisor being 6, but I'm looking for a quick optimized hack.

However, since this is meant to be used for a decision test, and not to actually to use the result of the division (except for testing), I can probably multiply for my target check and test if it's >= than that.
0 x

User avatar
Ast A. Moore
Manic Miner
Posts: 342
Joined: Mon Nov 13, 2017 3:16 pm

Re: Fastest Divide by 6

Post by Ast A. Moore » Sun Dec 31, 2017 3:37 pm

Keep subtracting 6 in a loop until Carry is set?

Code: Select all

	ld a,252
	ld c,255
loop	inc c
	sub 6
	jr nc,loop
Last edited by Ast A. Moore on Sun Dec 31, 2017 4:47 pm, edited 1 time in total.
0 x
Every man should plant a tree, build a house, and write a ZX Spectrum game.

Author of A Yankee in Iraq, a 50 fps shoot-’em-up—the first game to utilize the floating bus on the +2A/+3,
and zasm Z80 Assembler syntax highlighter.

User avatar
Mike Davies
Dizzy
Posts: 92
Joined: Mon Nov 13, 2017 10:11 am

Re: Fastest Divide by 6

Post by Mike Davies » Sun Dec 31, 2017 4:02 pm

Something from left-field: Since 6 is half-way between 8 and 4, the result of dividing by 6 should be halfway between dividing by 4 and 8. How about an algorithm like:

* Divide the number by 4 (>>2)
* Divide the number by 8 (>>3)
* Add the two shifted results together
* Divide this sum by 2 (>>1)
0 x

User avatar
Ast A. Moore
Manic Miner
Posts: 342
Joined: Mon Nov 13, 2017 3:16 pm

Re: Fastest Divide by 6

Post by Ast A. Moore » Sun Dec 31, 2017 4:18 pm

Mike Davies wrote:
Sun Dec 31, 2017 4:02 pm
* Divide the number by 4 (>>2)
* Divide the number by 8 (>>3)
* Add the two shifted results together
* Divide this sum by 2 (>>1)
That last shift will destroy the result for numbers less than 8.
0 x
Every man should plant a tree, build a house, and write a ZX Spectrum game.

Author of A Yankee in Iraq, a 50 fps shoot-’em-up—the first game to utilize the floating bus on the +2A/+3,
and zasm Z80 Assembler syntax highlighter.

Hikaru
Microbot
Posts: 100
Joined: Mon Nov 13, 2017 1:42 pm
Location: Russia
Contact:

Re: Fastest Divide by 6

Post by Hikaru » Sun Dec 31, 2017 4:40 pm

IIRC division by 3 is the same as multiplication by #55. Then you can shift the result right once to get division by 6. Not sure if that helps?

Edit: seems like it's actually #55+1 for more accurate rounding, or something.

This seems to work:

Code: Select all

;In: C = dividend
;Out: H = quotient
	ld l,c
	ld h,0
	ld b,h
	add hl,hl
	add hl,hl
	add hl,bc
	add hl,hl
	add hl,hl
	add hl,bc
	add hl,hl
	add hl,bc
	add hl,hl
	add hl,bc
	srl h
0 x
Inactive account

User avatar
RMartins
Manic Miner
Posts: 258
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins » Sun Dec 31, 2017 5:19 pm

Hikaru wrote:
Sun Dec 31, 2017 4:40 pm
IIRC division by 3 is the same as multiplication by #55. Then you can shift the result right once to get division by 6. Not sure if that helps?

Edit: seems like it's actually #55+1 for more accurate rounding, or something.

This seems to work:

Code: Select all

;In: C = dividend
;Out: H = quotient
	ld l,c
	ld h,0
	ld b,h
	add hl,hl
	add hl,hl
	add hl,bc
	add hl,hl
	add hl,hl
	add hl,bc
	add hl,hl
	add hl,bc
	add hl,hl
	add hl,bc
	srl h
Actually I found this for divisions by 10
http://z80-heaven.wikidot.com/math#toc25

10 bytes (and 81 t-states). It divides E by 10, returning the result in H :

e_div_10:
;returns result in H
ld d,0
ld h,d \ ld l,e
add hl,hl
add hl,de
add hl,hl
add hl,hl
add hl,de
add hl,hl
From by understanding of it, It actually mutiplies by 26 (=~256/10)), and gets the high part only.
So it's basically, multiplying by a value that will get you the required division, once we divide by 256 (which is just to get the high part).

This can probably be done with other division values.

Probably if multiplying by 42 (=~256/6) it will probably work.

Going to make some calcs on Excell next :)

UPDATE:
It almost works, until 60, it works for all values, except when dividign exact multiples of 6.
There is the factor that the error (fractional part of division 256/6), keeps adding up.

If mutiplying by 43 (42+1), it works flawlessly until a dividend of 130, where it starts to fail after 131, due to rounding error again.

For my own purposes, I only need something that works between 0 and 77.

This is to detected a condition, when a player starts to add up combos.
130 is enough for my case, since playfield is 07x11, so, at most a usar can make a combo of 77 items.
Last edited by RMartins on Sun Dec 31, 2017 5:59 pm, edited 2 times in total.
0 x

User avatar
RMartins
Manic Miner
Posts: 258
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins » Sun Dec 31, 2017 5:48 pm

Mike Davies wrote:
Sun Dec 31, 2017 4:02 pm
Something from left-field: Since 6 is half-way between 8 and 4, the result of dividing by 6 should be halfway between dividing by 4 and 8. How about an algorithm like:

* Divide the number by 4 (>>2)
* Divide the number by 8 (>>3)
* Add the two shifted results together
* Divide this sum by 2 (>>1)
Nice thinking :)
Ast A. Moore wrote:
Sun Dec 31, 2017 4:18 pm
Mike Davies wrote:
Sun Dec 31, 2017 4:02 pm
* Divide the number by 4 (>>2)
* Divide the number by 8 (>>3)
* Add the two shifted results together
* Divide this sum by 2 (>>1)
That last shift will destroy the result for numbers less than 8.
For my case, that might actually work, if I test for that specific case.
I have to check.
0 x

User avatar
RMartins
Manic Miner
Posts: 258
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins » Sun Dec 31, 2017 5:51 pm

Ast A. Moore wrote:
Sun Dec 31, 2017 3:37 pm
Keep subtracting 6 in a loop until Carry is set?

Code: Select all

	ld a,252
	ld c,255
loop	inc c
	sub 6
	jr nc,loop
This obviously works, since it's how division logically works.

However, for large dividend and small divisor, it takes a lot longer to reach the result.
I prefer, something fast, and of fixed processing length.
0 x

User avatar
R-Tape
Site Admin
Posts: 910
Joined: Thu Nov 09, 2017 11:46 am

Re: Fastest Divide by 6

Post by R-Tape » Sun Dec 31, 2017 5:58 pm

RMartins wrote:
Sun Dec 31, 2017 5:51 pm
Ast A. Moore wrote:
Sun Dec 31, 2017 3:37 pm
Keep subtracting 6 in a loop until Carry is set?

Code: Select all

	ld a,252
	ld c,255
loop	inc c
	sub 6
	jr nc,loop
This obviously works, since it's how division logically works.

However, for large dividend and small divisor, it takes a lot longer to reach the result.
I prefer, something fast, and of fixed processing length.
It doesn't solve your problem but preloading B with 6 and doing SUB B would of course be quicker :-)

Is this only for numbers 0-255? If so I wonder if Mike's solution could be the fastest, with a precheck of =6,7 or less.

EDIT - sorry I see you've already responded to that.
0 x

User avatar
R-Tape
Site Admin
Posts: 910
Joined: Thu Nov 09, 2017 11:46 am

Re: Fastest Divide by 6

Post by R-Tape » Sun Dec 31, 2017 6:22 pm

Code: Select all

	srl a
	srl a	;/4
	ld c,a
	srl a	;/8
	add a,c
	srl a
	ret
Doesn't work, e.g. it returns 255 with 47, not 42.
0 x

Post Reply