It is currently Mon Jul 23, 2018 5:07 am

 All times are UTC - 7 hours

 Page 1 of 1 [ 12 posts ]
 Print view Previous topic | Next topic
Author Message
 Posted: Tue Jul 25, 2017 12:21 am

Joined: Mon Jul 03, 2017 4:37 pm
Posts: 123
Does anyone happen to have a general algorithm for dividing by 10 and by 6 using shifts/addition? debating on whether to go this direction, or to code it into a table...

-Thom

Top

 Posted: Tue Jul 25, 2017 12:46 am

Joined: Fri Feb 27, 2009 2:35 pm
Posts: 281
Location: Fort Wayne, Indiana
The big Unsigned Integer Division Routines thread has routines for division by 6 and 10.

Top

 Posted: Tue Jul 25, 2017 6:23 am

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4056
8-bit dividing by 10 is the same as doing 16-bit multiplication by 0x1A (00011010), then discarding the low byte. So that's x << 4 + x << 3 + x << 1 in 16-bit math.
Dividing by 6 is multiply by 0x2B (00101011), or x << 5 + x << 3 + x << 1 + x.
16-bit shifts and adds take up code and time.
Then there's the really stupid way to divide, subtracting in a loop, if you don't care about speed, it's a decent way.

But lookup tables are really cheap, just 256 bytes of ROM for 8-bit math.

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

Top

 Posted: Tue Jul 25, 2017 9:09 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6431
Dwedit wrote:
8-bit dividing by 10 is the same as doing 16-bit multiplication by 0x1A (00011010), then discarding the low byte. So that's x << 4 + x << 3 + x << 1 in 16-bit math.
Dividing by 6 is multiply by 0x2B (00101011), or x << 5 + x << 3 + x << 1 + x.
16-bit shifts and adds take up code and time.

To clarify, this is a fixed point approximation technique. The results are not entirely accurate.

The approximation works because a division by 256 is "cheap", so you can rescale the input with a pre-multiply.

Code:
x / d =  x * a / 256
d = a / 256
a = 256 / d

d = 10 --> a = 256 / 10 = 25.6
x / 10 = x * 25.6 / 256

d =  6 --> a = 256 /  6 = 42.666...

You will notice that these are not exactly 26 (0x1A) or 43 (0x2B). This is why it's an approximation, and you will find the result is off by 1 in some cases:
Code:
⌊ 69 / 10 ⌋ = 6          (6.9)
⌊ 69 * 26 / 256 ⌋ = 7    (7.0078125)

Depending on whether you need perfect results or not, this may not be an acceptable compromise. You could increase it to 24 bits for more precision, or in some cases you might be able to adjust some errors by carefully adding a bias value.

Dwedit, I'm curious why you offered these numbers in hexadecimal and binary but not decimal. What significance do they have in hex/bin?

Top

 Posted: Tue Jul 25, 2017 9:30 am

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7329
Location: Seattle
I'm arbitrarily going to guess that the OP is either converting frames or seconds to the next larger unit ... perhaps, rather than implementing division, it makes sense to store the time in BCsexagesimal ?

Top

 Posted: Tue Jul 25, 2017 9:34 am

Joined: Mon Jul 03, 2017 4:37 pm
Posts: 123
(this is for Wizard of Wor)

Nah, I just need to be able to calculate from a sprite position the nearest dungeon box that he's in (the dungeon is implemented as a 10x6 array of squares), so that I can implement collision detection and the like.

-Thom

Top

 Posted: Tue Jul 25, 2017 10:04 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20291
Location: NE Indiana, USA (NTSC)
So it's division by 24 (which may involve division by 3 or 6 as an intermediate step) to convert from sprite coordinates to metatile coordinates, then multiply by 10 or by 6 (depending on whether row-major or column-major) to convert metatile coordinates to an address in the backing map. I don't see where division by 10 enters into it, except during conversion of a score to decimal.

Top

 Posted: Tue Jul 25, 2017 10:11 am

Joined: Mon Jul 03, 2017 4:37 pm
Posts: 123
tepples wrote:
So it's division by 24 (which may involve division by 3 or 6 as an intermediate step) to convert from sprite coordinates to metatile coordinates, then multiply by 10 or by 6 (depending on whether row-major or column-major) to convert metatile coordinates to an address in the backing map. I don't see where division by 10 enters into it, except during conversion of a score to decimal.

Oh ok, I was thinking to derive the X and Y values seperately, but.. ok..

-Thom

Top

 Posted: Tue Jul 25, 2017 11:21 am

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4056
rainwarrior wrote:
Dwedit, I'm curious why you offered these numbers in hexadecimal and binary but not decimal. What significance do they have in hex/bin?

In binary, you can see the sequence of shifts and adds to do the multiply. Multiplying by 00110011 means x << 0 + x << 1 + x << 4 + x << 5 because those bits are set in the binary number.
And hex because I'm used to expressing reciprocal approximations in hex. On 32-bit arm, I'd always do 0x100000000 / x, then add 1, and use UMULL to do division. Here I did 0x100 / x + 1, but I might have needed some more precision here.

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

Top

 Posted: Tue Jul 25, 2017 12:12 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6431
Dwedit wrote:
In binary, you can see the sequence of shifts and adds to do the multiply.

Ah, yes that makes sense.

Top

 Posted: Tue Jul 25, 2017 4:02 pm

Joined: Mon Jul 03, 2017 4:37 pm
Posts: 123
Wound up using omegamatrix's div by 24 routine:

Code:
;Divide by 24
;15 bytes, 27 cycles
_div24:   lsr
lsr
lsr
sta   temp
lsr
lsr
ror
lsr
ror
lsr
rts

As it turns out, I was being derp by not realizing that I needed to count pixels, not boxes for the divisor, thanks tepples.

-Thom

Top

 Posted: Tue Aug 01, 2017 5:37 pm

Joined: Mon Jul 03, 2017 4:37 pm
Posts: 123
Is there a complimentary routine for returning the modulus? I'm needing to do fine adjustment of the division to indicate whether I am actually as far into a box as I can be physically.

-Thom

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 12 posts ]

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: No registered users and 3 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki