## Fastest Divide by 6

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

### Re: Fastest Divide by 6

R-Tape wrote:
Sun Dec 31, 2017 5:58 pm
...
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.
I update above, but I only require it to work between 0 and 77.

Mike solution might be better, if it requires less registers.

Code: Select all

``````; Divide L by 6
;============
; Inputs:
; L = Dividend
;----------------
; implemnetation : multiplies by 43 (=~ 256/6 +1), and returns the high byte (H)
; NOTE: 43 = 32 + 8 + 2 +1
; OR  using add and subtracts in sequence: 	2	4	5	10	11	22	44	43
LD	H, 0
LD	D, H		; DE = HL
LD	E, L
SBC	HL, DE	; x43
; result in H
``````
Any one with a shorter (faster) solution, or less registers ?
0 x

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

### Re: Fastest Divide by 6

Well, if your range is up to 77, then this will be 3 T states faster (dividend goes into A):

Code: Select all

``````	LD	H, 0
LD	D, H		; DE = HL
ld e,a
ld l,a
SBC	HL, DE	; x43
``````
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.

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

### Re: Fastest Divide by 6

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.
Actually, there is a larger flaw in this reasoning.

For example: Value 16

16/4 = 4
16/8 = 2
4+2 = 6
6/2 = 3, when it should have been 2, since 16/6 = 2.xx

The Error, is that we need to add to (/4 result ), half of the difference (between /4 - /8 results).
In that case it will be correct.

UPDATE:
Actually it doesn't work either, because it's rquivalent.

The problem seems to be the assumption that Divison by 6, is in the middle of division by 4 and by 8, which apparently is not true, although our common sense, might assume this to be true.
1 x

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

### Re: Fastest Divide by 6

Ast A. Moore wrote:
Sun Dec 31, 2017 6:52 pm
Well, if your range is up to 77, then this will be 3 T states faster (dividend goes into A):

Code: Select all

``````	LD	H, 0
LD	D, H		; DE = HL
ld e,a
ld l,a
SBC	HL, DE	; x43
``````
Yes, of course, but I meant it more in the sense of other ways to reach the result.
For example, other ways to multiply by 43, since several possible combinations exist (like the binary one (listed in my comments), and others.

Another example, using this sequence: 2 4 8 16 32 48 44 43
NOTE: This one, requires to keep x4 and x1 as reference to subtract later.
0 x

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

### Re: Fastest Divide by 6

I also realised the assumption is wrong, but I can't help but feel the div/8 and div/4 idea is a starting point. After an hour's head scratching I haven't managed it though.

As it's new year you should treat yourself to a nice 77 byte, word aligned lookup table
1 x

AndyC
Microbot
Posts: 197
Joined: Mon Nov 13, 2017 5:12 am

### Re: Fastest Divide by 6

RMartins wrote:
Sun Dec 31, 2017 6:25 pm
I update above, but I only require it to work between 0 and 77.
In that case:

LD H,table_of_results /256
LD L,A
LD A,(HL)

table_of_results
.ALIGN 256
DEFB 0,0,0,0,0,1 ...etc...
0 x

Joefish
Manic Miner
Posts: 370
Joined: Tue Nov 14, 2017 10:26 am

### Re: Fastest Divide by 6

Yes, it doesn't work.
The quickest way to divide by a fixed number N is to work out 1/N and multiply. You can scale 1/6 up by 256 as in that previous example.

The 4 & 8 thing doesn't easily work because you're dealing with 1/4 and 1/6 and 1/8, which are not evenly spaced. Think of them as 6/24 and 4/24 and 3/24 and you can see the spacing is not regular. You can work out 1/3 and halve the result to get 1/6, but there's no shortcut to doing that fundamental factor of 1/3.

256/3 = 85, which is 01010101 in binary. So you can hard-code a copy, then two shifts and an add three times, which gives you 1/3 but 8 bits higher than you started with. Shift right to get 1/6.
1 x

Kweepa
Microbot
Posts: 189
Joined: Sat Feb 03, 2018 6:14 pm
Location: Austin, Texas

### Re: Fastest Divide by 6

The book Hacker’s Delight has code for many integer divisions, including 6:
http://www.hackersdelight.org/divcMore.pdf
1 x

Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

### Re: Fastest Divide by 6

https://www.jjj.de/fxt/fxtbook.pdf

This is also another excellent book.
2 x

Kweepa
Microbot
Posts: 189
Joined: Sat Feb 03, 2018 6:14 pm
Location: Austin, Texas

### Re: Fastest Divide by 6

Ooh, interesting! I went straight to Amazon to buy that book... then decided that maybe the pdf was good enough. \$95.60?!
0 x