A 6502 divide routine

[wsimms]

The worst cases in the divide routine that I have presented occur, ironically enough, when the divisor is a power of two. And the worst of the worst occurs when the divisor is 1 and the dividend is 32767. This case requires almost 2000 cycles to produce the result. For this reason, it seems necessary to prefix the routine I have presented with a check looking for divide by 1. It may also be useful to check for the case of divide by (small) powers of 2.

What I dislike about the routine is the wide variability in execution speed and the excessively large cycle counts for certain "bad" inputs (divisor is a small power of 2). What I like about the routine is the conceptual simplicity of its operation and the very small cycle counts for certain "good" inputs (divisor > dividend is an example of "good" inputs)..

I hope to post an updated version later this week or early next week.

[dmsc]

wsimms wrote:

The worst cases in the divide routine that I have presented occur, ironically enough, when the divisor is a power of two. And the worst of the worst occurs when the divisor is 1 and the dividend is 32767. This case requires almost 2000 cycles to produce the result. For this reason, it seems necessary to prefix the routine I have presented with a check looking for divide by 1. It may also be useful to check for the case of divide by (small) powers of 2.

The code from CC65 hast two cases, a full 16 bit divisor or an 8 bit divisor:
https://github.com/cc65/cc65/blob/maste ... udiv.s#L31

Perhaps you could do the same in your code?

Have Fun!

[BigEd]

That's an interesting note about worst-case inputs!

[barnacle]

And a multiple level thingie too: not only do (should) you care about program size and execution time, but you need to worry about pathological inputs, and even what is the distribution of those inputs... it does rather suggest that for efficiency you need to have very good knowledge about the actual data your program will be dealing with.

And of course you have to think about the size of your parameters: 8/16/24/32... bits, and whether they're signed or not. Arithmetic is hard, and division is perhaps the hardest bit of it.

For my Tiny Basic, I need small. It doesn't even provide protection for div/0, but it handles everything in - I think - a reasonably consistent time.

(I am reminded of a free version of PIC's C compiler, ten or so years ago, which implemented <<8 by doing <<1 eight times... while the paid version did the obvious and much faster byte shift.)

Neil