Fastest Divide by 6

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

Re: Fastest Divide by 6

Post by RMartins » Sun Dec 31, 2017 6:25 pm

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
ADD	HL, HL	; x02
ADD	HL, HL	; x04
ADD	HL, DE	; x05
ADD	HL, HL	; x10
ADD	HL, DE	; x11
ADD	HL, HL	; x22
ADD	HL, HL	; x44
SBC	HL, DE	; x43
; result in H
Any one with a shorter (faster) solution, or less registers ?
0 x

User avatar
Ast A. Moore
Microbot
Posts: 150
Joined: Mon Nov 13, 2017 3:16 pm

Re: Fastest Divide by 6

Post by Ast A. Moore » 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
	add a,a
	ld l,a
	ADD	HL, HL	; x04
	ADD	HL, DE	; x05
	ADD	HL, HL	; x10
	ADD	HL, DE	; x11
	ADD	HL, HL	; x22
	ADD	HL, HL	; x44
	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.

User avatar
RMartins
Microbot
Posts: 106
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins » Sun Dec 31, 2017 6:57 pm

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

User avatar
RMartins
Microbot
Posts: 106
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

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

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
	add a,a
	ld l,a
	ADD	HL, HL	; x04
	ADD	HL, DE	; x05
	ADD	HL, HL	; x10
	ADD	HL, DE	; x11
	ADD	HL, HL	; x22
	ADD	HL, HL	; x44
	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

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

Re: Fastest Divide by 6

Post by R-Tape » Mon Jan 01, 2018 12:29 pm

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 :mrgreen:
1 x

AndyC
Berk
Posts: 47
Joined: Mon Nov 13, 2017 5:12 am

Re: Fastest Divide by 6

Post by AndyC » Mon Jan 01, 2018 12:48 pm

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
Dizzy
Posts: 83
Joined: Tue Nov 14, 2017 10:26 am

Re: Fastest Divide by 6

Post by Joefish » Mon Jan 01, 2018 4:28 pm

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

Post Reply