FAST 6502 DIVIDE BY 14?

aiia...@gmail.com

unread,

Aug 14, 2012, 4:09:29 PM8/14/12

to

i'VE seen tricks for doing different divides
using 6502...

are there any for divide by 14?

input = 1 byte
output = byte / 14, remainder

Rich

aiia...@gmail.com

unread,

Aug 14, 2012, 4:14:43 PM8/14/12

to

On Tuesday, August 14, 2012 1:09:29 PM UTC-7, (unknown) wrote:
> i'VE seen tricks for doing different divides
>
> using 6502...
>
>
>
> are there any for divide by 14?

I'm going to do it with a table, but it would be interesting to see how the divide by X algorithms are figured out.

Rich

BLuRry

unread,

Aug 14, 2012, 4:21:56 PM8/14/12

to

Consider divide by 14 as a divide by 2 (easy!) and then by 7.

Divide by 7:
DIVIDE_BY_SEVEN:
LDA BYTE
LSR
LSR
LSR
ADC BYTE
ROR
LSR
LSR
ADC BYTE
ROR
LSR
LSR
RTS

BLuRry

unread,

Aug 14, 2012, 4:24:01 PM8/14/12

to

A table would probably be faster though. It would take only a few bytes more to store a table for values 0-20 than it would to write the divide by 7 code. But storing a div7 table would save some room, if you can stand the extra opcode for shifting A one place to the right before looking up the table.

Egan Ford

unread,

Aug 14, 2012, 4:39:24 PM8/14/12

to

BLuRry beat me to it:

lda #$5F ; load dividend in a
jsr div14 ; /14 it
sta result ; result is in a
rts

div14:
sta dividend
lsr
lsr
lsr
adc dividend
ror
lsr
lsr
adc dividend
ror
lsr
lsr ;div by 7
lsr ;div by 2 (14)
rts

Egan Ford

unread,

Aug 14, 2012, 4:45:47 PM8/14/12

to

Here is a better one that give you /7 and /14.

div14:
lsr
div7:

sta dividend
lsr
lsr
lsr
adc dividend
ror
lsr
lsr
adc dividend
ror
lsr
lsr

rts

Remainder is missing. Is that required?

aiia...@gmail.com

unread,

Aug 14, 2012, 4:53:07 PM8/14/12

to

yUP...

How do you get from divide by 7, or divide by 14, to the above code? I've seen descriptions of how to do it in 6502 assembly language textbooks, but I've never understood it.

Rich

Egan Ford

unread,

Aug 14, 2012, 4:54:32 PM8/14/12

to

More info here: http://www.txbobsc.com/aal/1984/aal8412.html#a5

Egan Ford

unread,

Aug 14, 2012, 4:59:59 PM8/14/12

to

1/7 = 1/8 + 1/64 + 1/512 + 1/4096 + ...

This trick works for any power of 2 less 1, e.g. 3, 7, 15, etc...

Egan Ford

unread,

Aug 14, 2012, 5:08:26 PM8/14/12

to

On 8/14/12 2:53 PM, aiia...@gmail.com wrote:

> How do you get from divide by 7, or divide by 14, to the above code?

More info: http://www.hackersdelight.org/divcMore.pdf

I highly recommend this book.

Antoine Vignau

unread,

Aug 14, 2012, 6:38:20 PM8/14/12

to

Fourteen, just like the width of your Mario objects ;-)
antoine

Michael J. Mahon

unread,

Aug 14, 2012, 8:14:14 PM8/14/12

to

If the quotient is known to be small, a simple repeated subtraction wil
yield both the quotient and the remainder. ;-)

If it really needs to be fast, then tables can't be beat. If it's in
between and the remainder is unnecessary, then the multiply-by- reciprocal
approach is great.

-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

aiia...@gmail.com

unread,

Aug 17, 2012, 12:25:29 AM8/17/12

to

On Tuesday, August 14, 2012 3:38:20 PM UTC-7, Antoine Vignau wrote:
> Fourteen, just like the width of your Mario objects ;-)
>
> antoine

Yes, I hacked some basic code to do collision detection, draw mario, make him jump. Now I'm converting all to assembly (except for a small basic program that loads levels, sprites, and CALLS 6502 program)

I need to work on how mario moves. I'm moving him one pixel, but his arms and legs are flailing like he's running a marathon. I think move two pixels, and not change the frame of animation so often.

Rich