6502.org

I am looking for some esy way to divide 16bit variable by 40. Variable is used to point to the test cursor location in VRAM memory. Screen size is 24x40 so I need divide cursor value by 40 do determine number of current line. Cursor value will never exceed 960, so result will always be 1 byte number.
What is the simplest method?

Curiously I'm in the process of implementing a memory mapped text display, however my code always knows exactly where the cursor is, so I never have to work the reverse.

However one approach: Start at zero in a 16-bit variable, and add 40 into it in a loop and count how many times you add 40 into it before it's > the 16-bit number you have for the cursor position... You could also subtract 40 from your 16-bit number until it goes negative. Slightly faster, maybe, divide by 4 (2 x shifts) then divide by 10 (ie. subtract 10 in a loop) Not sure which way might be the quickest but it might be easier than implementing a generic division... always trade off's ...

Worst case on the div 4 then sub 10:

959 divide by 4 is 239, the subtract 10 from that in a loop will count 24 times until it's < 0, so the answer is that you're on line 23. (0-23)

the other end of the scale; 41 - divide by 4 to get 10, subtract 10 to get 2 (when it's < 0), so line 1.

You can divide by 10 quicker if you divide by 100 first if the number is >= 100. Both speed and code complexity goes up though.

There are other ways but a lot will depend on your needs - small code, fast code, easy to read code, or ... ?

-Gordon

There must be many ways! Traditional is a shift and compare, with an optional subtract.

But you could start by subtracting 640 (if you can) then 320, 160, 80, and finally 40. The first two of those are two-byte operations, the final three need only one byte. Each time you get 1 bit of your 5 bit result.

Another way, perhaps. In Acorn's MOS there's a 25 entry table of the multiples of 40 from 0*40 to 24*40. That's 50 bytes. By searching that table you can find out which multiple of 40 fits the number you have. (A binary search will be quickest. A linear search is equivalent to repeated subtractions of 40, but might be faster.)
https://tobylobster.github.io/mos/mos/S-s4.html#SP8

First divide by 8, which gets you into the range 0-120 (fits in 1 byte), then go from there - either try subtracting 80, 40, 20, 10, 5 in turn, do a table search, or even use a lookup table if you want maximum speed.

An excellent first move!

Isn't there a funky trick using the BCD mode to divide by 10? I don't recall the details though.

It would be just a shift-right four bit positions; but that assumes the number is already in BCD. If it's not, you'd have to convert to and from, which is far less efficient than just dividing in the manner discussed above.

archive.org to the rescue: https://web.archive.org/web/20210120031 ... =2&t=11336

Charlie and I arrived at an 18 byte + RTS solution for PETTIL that's going to be hard to beat for code size, and it gives you the remainder for (almost) free. It's not very fast, but there are attempts further up-thread from Omegamatrix that are larger and faster.

viewtopic.php?f=2&t=3051&p=36767&hilit= ... sor#p36767

This is the DivideBy5 from the NesDev:

The ADC #13 can be removed without affecting the result for numbers below 130, which they will be in this case.
It's almost, but not quite, calculating the high byte of A*51. Using ADC with whatever the previous LSR left in carry complicates things a little: these steps round instead of truncating, and the result will be slightly higher than A*51. That's good, because we actually want to multiply by 256/5 = 51.2

The quotient will be below 130, but the OP needs at least a 10-bit numerator, so ... oh, I see, divide by eight first, and your numerator is only seven bits. That's definitely faster than my solution, but it's bigger and sends the remainder to /dev/null.