It is currently Tue Dec 12, 2017 7:05 am

 All times are UTC - 7 hours

### Forum rules

Related:
• For making cartridges of your Super NES games, see Reproduction.

 Page 1 of 1 [ 14 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: 16/16-bit divisionPosted: Mon Jul 03, 2017 8:40 pm

Joined: Wed May 19, 2010 6:12 pm
Posts: 2421
Anybody know how this would be done? The easiest way I know of is by shifting the denominator right until it's less than 256, and then shift the quotient right by the same number of times.

Is there a more accurate way of doing this?

Top

 Post subject: Re: 16/16-bit divisionPosted: Mon Jul 03, 2017 9:53 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19334
Location: NE Indiana, USA (NTSC)
Top

 Post subject: Re: 16/16-bit divisionPosted: Tue Jul 04, 2017 12:55 am

Joined: Mon Mar 30, 2015 10:14 am
Posts: 206
http://codebase64.org/doku.php?id=base:6502_6510_maths

But no magic, you need LUT if you want some speed .

Top

 Post subject: Re: 16/16-bit divisionPosted: Tue Jul 04, 2017 8:30 am

Joined: Wed May 19, 2010 6:12 pm
Posts: 2421
I was wondering if there was a way that makes use of the SNES's division registers.

Top

 Post subject: Re: 16/16-bit divisionPosted: Tue Jul 04, 2017 8:40 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19334
Location: NE Indiana, USA (NTSC)
There probably isn't a way to get exact division by an arbitrary 16-bit number out of the memory controller's divider. So at this point, you may have the XY problem: you have a goal, you think a step (division by a 16-bit number) is the way to go about that goal, and you ask about the step without describing the goal. What are you trying to accomplish with this division?

Top

 Post subject: Re: 16/16-bit divisionPosted: Tue Jul 04, 2017 9:13 am

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
I was recently looking for a good way to do 16/16-bit division to calculate the relative angle between the player and game objects in my raycaster, and was amazed to find out that log2(x/y) = log2(x) - log2(y)! That works well because to find an angle you only need the ratio between x and y, so the actual quotient isn't really needed, just its logarithm will do.

Yeah, shame on me for not knowing how to use logarithms before (I was never good at this in school - if I knew this would help me program games one day, I'd have paid more attention), but I was just glad to find out that with a couple of tables I could turn an expensive division into a simple subtraction.

I ended up finding the answer to my problem myself (and I had probably seen this trick before, but it must've flown over my head), but if I had asked for help, asking "how can I find this angle" vs. "how can I do a 16/16-bit division" could've made all the difference.

To keep the tables small I ended up going with 11/11-bit though, which works perfectly for my needs.

Top

 Post subject: Re: 16/16-bit divisionPosted: Tue Jul 04, 2017 10:48 am

Joined: Wed May 19, 2010 6:12 pm
Posts: 2421
I have an idea for this:

Shift the denominator right until it's odd. If the shifted denominator is less than 256, use the division registers. Shift the result left by the same amount of bits as the you shifted the denominator.

If the shifted denominator is 256 or larger, use software division. Because the denominator is 256 or larger, the result has to be less than 256, so only 8 bits are needed for the result.

Now that I think about it, I can reduce the number of compares/subtracts by the number of times the denominator is shifted.

tepples wrote:
There probably isn't a way to get exact division by an arbitrary 16-bit number out of the memory controller's divider. So at this point, you may have the XY problem: you have a goal, you think a step (division by a 16-bit number) is the way to go about that goal, and you ask about the step without describing the goal. What are you trying to accomplish with this division?

Just for fun, pretty much. I might use it as a go-to division routine if I'm in a hurry to get something done.

Top

 Post subject: Re: 16/16-bit divisionPosted: Wed Jul 05, 2017 7:49 am

Joined: Mon Jul 01, 2013 11:25 am
Posts: 228
tokumaru wrote:
I was recently looking for a good way to do 16/16-bit division to calculate the relative angle between the player and game objects in my raycaster, and was amazed to find out that log2(x/y) = log2(x) - log2(y)! That works well because to find an angle you only need the ratio between x and y, so the actual quotient isn't really needed, just its logarithm will do.

Yeah, shame on me for not knowing how to use logarithms before (I was never good at this in school - if I knew this would help me program games one day, I'd have paid more attention), but I was just glad to find out that with a couple of tables I could turn an expensive division into a simple subtraction.

I ended up finding the answer to my problem myself (and I had probably seen this trick before, but it must've flown over my head), but if I had asked for help, asking "how can I find this angle" vs. "how can I do a 16/16-bit division" could've made all the difference.

To keep the tables small I ended up going with 11/11-bit though, which works perfectly for my needs.

The problem of using log is that :
- it doesn't work on signed number (ok you can eventually offset them)
- accuracy is poor for high number

But still log is very useful for fast multiply (become an addition) or a division (become a subtraction)

Top

 Post subject: Re: 16/16-bit divisionPosted: Thu Jul 06, 2017 3:20 pm

Joined: Fri Jul 04, 2014 9:31 pm
Posts: 818
Garth Wilson has suggested using a table of inverses to feed into a multiplication. He even provides such a table on his scaled-integer page.

Top

 Post subject: Re: 16/16-bit divisionPosted: Sat Jul 08, 2017 3:32 am

Joined: Tue Feb 07, 2017 2:03 am
Posts: 262
do you want
u16/u16 = u16
u16/u16 = u8
s16/s16 = s16
s16/s16 = s8
?

Top

 Post subject: Re: 16/16-bit divisionPosted: Mon Jul 31, 2017 3:17 pm

Joined: Wed May 19, 2010 6:12 pm
Posts: 2421
I figured out you can take the equation Y=X/(A+B), rearrange it as Y = (X - BY)/A, and solve it recursively.

Top

 Post subject: Re: 16/16-bit divisionPosted: Wed Aug 02, 2017 4:34 pm

Joined: Fri Feb 24, 2012 12:09 pm
Posts: 535
The Playstation hardware is using this fast (but slightly inaccurate) division method http://problemkaputt.de/psx-spx.htm#gte ... inaccuracy it's based on Unsigned Newton-Raphson (UNR) algorithm, and comes up with one table read, plus three multiplications, plus some shift/add/sub operations.

The way how it's done there isn't exactly what you want: the input is two unsigned 16bit values... but it does multiply one of the values by 20000h before dividing it, and returns a 17bit result. But it shouldn't be too difficult to remove the multiply by 20000h, and tweak it to return a 16bit value.

For the unsigned multiplies, the SNES hardware supports 8bit*8bit=16bit (via CPU), or 7bit*15bit=22bit (via PPU, with sign bits set to zero). So you'll internally need more than three multiplications on the SNES. When reducing accuary & dropping some bits... maybe you could get away with four PPU operations (two for the first two multiplies, and another two for the final multiply with bigger operands).

Top

 Post subject: Re: 16/16-bit divisionPosted: Thu Aug 03, 2017 5:01 am

Joined: Mon Jan 23, 2006 7:47 am
Posts: 79
The APU can also multiply & divide.

Top

 Post subject: Re: 16/16-bit divisionPosted: Thu Aug 03, 2017 3:08 pm

Joined: Wed May 19, 2010 6:12 pm
Posts: 2421
I think I got it this time.

Do to the thing I said in the OP. Then multiply the quotient by the divisor, and compare it to the dividend. If it's greater than the dividend, decrement the quotient by 1.

Top

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

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: Bing [Bot], lazygecko and 8 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       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