Easiest way to divide 16bit value by 40

[Atlantis]

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?

[drogon]

Atlantis wrote:

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

[BigEd]

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.

[BigEd]

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

[kernelthread]

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.

[BigEd]

An excellent first move!

[gfoot]

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

[GARTHWILSON]

After three shift-rights, you could divide by 5. NesDev forum member "Omegamatrix" has efficient 6502 routines to divide by any constant up to 32, at http://forums.nesdev.com/viewtopic.php?f=2&t=11336 . Unfortunately the NesDev forum was somehow heavily hijacked and damaged by spammers (which I warned the admins and mods about, but they didn't take me seriously), and the forum has been down for the last week while they try to repair the damage. Hopefully it will be back up, repaired, soon.

[GARTHWILSON]

gfoot wrote:

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.

[rwiker]

GARTHWILSON wrote:

After three shift-rights, you could divide by 5. NesDev forum member "Omegamatrix" has efficient 6502 routines to divide by any constant up to 32, at http://forums.nesdev.com/viewtopic.php?f=2&t=11336 . Unfortunately the NesDev forum was somehow heavily hijacked and damaged by spammers (which I warned the admins and mods about, but they didn't take me seriously), and the forum has been down for the last week while they try to repair the damage. Hopefully it will be back up, repaired, soon.

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

[barrym95838]

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

[BB8]

This is the DivideBy5 from the NesDev:

Code: Select all

  STA temp
  LSR
  ADC #13
  ADC temp
  ROR
  LSR
  LSR
  ADC temp
  ROR
  ADC temp
  ROR
  LSR
  LSR

[John West]

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

[barrym95838]

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.