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: 776
Joined: Thu Nov 16, 2017 3:26 pm

Fastest Divide by 6

Post by RMartins »

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.
User avatar
Ast A. Moore
Rick Dangerous
Posts: 2640
Joined: Mon Nov 13, 2017 3:16 pm

Re: Fastest Divide by 6

Post by Ast A. Moore »

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.
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
Microbot
Posts: 137
Joined: Mon Nov 13, 2017 10:11 am

Re: Fastest Divide by 6

Post by Mike Davies »

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)
User avatar
Ast A. Moore
Rick Dangerous
Posts: 2640
Joined: Mon Nov 13, 2017 3:16 pm

Re: Fastest Divide by 6

Post by Ast A. Moore »

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

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
Inactive account
User avatar
RMartins
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

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.
User avatar
RMartins
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

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.
User avatar
RMartins
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

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.
User avatar
R-Tape
Site Admin
Posts: 6353
Joined: Thu Nov 09, 2017 11:46 am

Re: Fastest Divide by 6

Post by R-Tape »

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.
User avatar
R-Tape
Site Admin
Posts: 6353
Joined: Thu Nov 09, 2017 11:46 am

Re: Fastest Divide by 6

Post by R-Tape »

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.
User avatar
RMartins
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

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 ?
User avatar
Ast A. Moore
Rick Dangerous
Posts: 2640
Joined: Mon Nov 13, 2017 3:16 pm

Re: Fastest Divide by 6

Post by Ast A. Moore »

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
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
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

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.
User avatar
RMartins
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

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.
User avatar
R-Tape
Site Admin
Posts: 6353
Joined: Thu Nov 09, 2017 11:46 am

Re: Fastest Divide by 6

Post by R-Tape »

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:
AndyC
Dynamite Dan
Posts: 1388
Joined: Mon Nov 13, 2017 5:12 am

Re: Fastest Divide by 6

Post by AndyC »

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...
User avatar
Joefish
Rick Dangerous
Posts: 2042
Joined: Tue Nov 14, 2017 10:26 am

Re: Fastest Divide by 6

Post by Joefish »

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.
User avatar
Kweepa
Manic Miner
Posts: 311
Joined: Sat Feb 03, 2018 6:14 pm
Location: Albuquerque, New Mexico

Re: Fastest Divide by 6

Post by Kweepa »

The book Hacker’s Delight has code for many integer divisions, including 6:
http://www.hackersdelight.org/divcMore.pdf
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Fastest Divide by 6

Post by Nomad »

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

This is also another excellent book.
User avatar
Kweepa
Manic Miner
Posts: 311
Joined: Sat Feb 03, 2018 6:14 pm
Location: Albuquerque, New Mexico

Re: Fastest Divide by 6

Post by Kweepa »

Ooh, interesting! I went straight to Amazon to buy that book... then decided that maybe the pdf was good enough. $95.60?!
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Fastest Divide by 6

Post by Nomad »

Kweepa wrote: Mon Feb 05, 2018 2:42 pm Ooh, interesting! I went straight to Amazon to buy that book... then decided that maybe the pdf was good enough. $95.60?!
That was my thought also.. I don't mind supporting authors when they are not wringing every dollar they can from you. :lol: That is my argument with a lot of academics - they want to be published but how many people ever get to read what they write? Probably a handful of libraries that are on grants buy these expensive books and its read by at most a few hundred people.

If they published with a regular publisher (assuming it was good enough to be picked up) or even if it was self published it could be released for a reasonable about and get a much wider circulation. There are tons of books like that just gathering dust with interesting approaches that could be useful but they are never going to be read by anyone that would actually put it to practical use its a great shame.

Springer are a good example, they have a computer science series that runs into the 7000 volume mark now but nobody I know outside of a university has heard of it, But then things have started to change recently because these publishers were forced to move into the 21 century and give subscribers a better deal.

anyway rant over. :lol:
Jonathan
Drutt
Posts: 11
Joined: Sun Feb 18, 2018 6:55 pm
Contact:

Re: Fastest Divide by 6

Post by Jonathan »

For the CPC version of AGD I just had to knock together a quick and simple routine to divide a screen coordinate held in the accumulator by 5. The routine I wrote was this:

Code: Select all

; Divide y coordinate by 5 to give block position.

div5   push bc             ; store bc.
       ld b,0              ; reset result.
       cp 80               ; more than 80?
       jr c,div5a          ; no.
       sub 80              ; subtract 80.
       set 4,b             ; set bit for 16.
div5a  cp 40               ; more than 40?
       jr c,div5b          ; no.
       sub 40              ; subtract 40.
       set 3,b             ; set bit for 8.
div5b  cp 20               ; more than 20?
       jr c,div5c          ; no.
       sub 20              ; subtract 20.
       set 2,b             ; set bit for 4.
div5c  cp 10               ; more than 10?
       jr c,div5d          ; no.
       sub 10              ; subtract 10.
       set 1,b             ; set bit for 2.
div5d  cp 5                ; more than 5?
       jr c,div5e          ; no.
       inc b               ; set bit for 1.
div5e  ld a,b              ; get result.
       pop bc              ; restore bc.
       ret
Not on Twitter, left the Spectrum scene on 4th December 2018. Thanks folks, it was a pleasure knowing you.
http://www.spanglefish.com/egghead/
http://arcadegamedesigner.proboards.com/
https://jonathan-cauldwell.itch.io/
User avatar
RMartins
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

If I'm not mistaken, that's the usual way to make a divison, bit by bit, except that in this case, it's optimized to match division by 5, since consecutive multiples of 5 are being checked.
Wall_Axe
Manic Miner
Posts: 492
Joined: Mon Nov 13, 2017 11:13 pm

Re: Fastest Divide by 6

Post by Wall_Axe »

why is the number being compared to 10,20,40?


for divide by 6 i was thinking, first see if the number is less than six, if yes,return zero
if no, add one to the result
then take away six from the number
then shift right until the 1st bit is set...so you are reducing the number down to the smallest
then just take away six until you are left with a number less than six
and adjust the answer with how many times you shifted right
User avatar
RMartins
Manic Miner
Posts: 776
Joined: Thu Nov 16, 2017 3:26 pm

Re: Fastest Divide by 6

Post by RMartins »

Wall_Axe wrote: Mon Feb 19, 2018 6:00 pm why is the number being compared to 10,20,40?
...
Those are just multiples of 5, that match the specific bit that will be set, if condition holds true.

40 / 5 = 8 (bit3)
20 / 5 = 4 (bit2)
10 / 5 = 2 (bit1)
Post Reply