## Fastest Divide by 6

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

### Fastest Divide by 6

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
LD	B, A	; Temp register for A*2
``````
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

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

### Re: Fastest Divide by 6

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.

Mike Davies
Microbot
Posts: 114
Joined: Mon Nov 13, 2017 10:11 am

### Re: Fastest Divide by 6

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

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

### Re: Fastest Divide by 6

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

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
srl h
``````
0 x
Inactive account

RMartins
Manic Miner
Posts: 331
Joined: Thu Nov 16, 2017 3:26 pm

### Re: Fastest Divide by 6

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
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
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

RMartins
Manic Miner
Posts: 331
Joined: Thu Nov 16, 2017 3:26 pm

### Re: Fastest Divide by 6

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

RMartins
Manic Miner
Posts: 331
Joined: Thu Nov 16, 2017 3:26 pm

### Re: Fastest Divide by 6

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

R-Tape
Posts: 1754
Joined: Thu Nov 09, 2017 11:46 am

### Re: Fastest Divide by 6

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

R-Tape
Posts: 1754
Joined: Thu Nov 09, 2017 11:46 am

### Re: Fastest Divide by 6

Code: Select all

``````	srl a
srl a	;/4
ld c,a
srl a	;/8