| |
TWW
Registered: Jul 2009
Posts: 545 |
Fractional Scaling - Math problem
Alright.
Say you got the fraction 44/93.
Then you want to scale it to a predetermined denominator of 128 which would give: 61/128 (rounded).
61 is found by calculating 44*128/93.
One multiplication and a division is a bit heavy if you plan to do real-time stuff.
The fastest way I have come up with so far is this:
Set up a 16 bit index table for 1-128 which gives the scaling factor of the denominator (i.e. 1,376 for 128/93). 7 bits for the whole number (1-128) and 9 bits for the decimals giving some accuracy.
Then multiply this with the original numerator to get the scaled numerator.
Still stuck with a small lookup-table (256b) and a 16 by 8 bit multiplication.
Any suggestions on how to do this faster (without spending 16k on a lookuptable)? |
|
... 14 posts hidden. Click here to view all posts....
|
| |
TWW
Registered: Jul 2009
Posts: 545 |
Alright, thanx, I see that we are more or less on about the same thing :-)
However I have an issue with accuracy which I want to flag:
Let's say you have the fraction 7/14 which you want to scale to x/255.
Calculating it directly it gives us x = 128 (rounded).
If we use a lookup table with 2 decimals we will get:
255/14 = 18,21
If we then multiply this with 7 we get the new numerator = 127,47 which unfortunately rounds to 127.
If we increase the amounts of decimals in our lookup table (8 bits is getting awfully small right about now) to 3 bits we get:
255/14 = 18,214
multiply with the numerator: 18,214 * 7 = 127,498 still not good enough.
So let's go crazy and do 4 decimals:
255/14 = 18,2143 (Rounded)
which gives: 18,2143 * 7 = 127,5001 and we finally got it right, right?
let's increase the accuract to 7 decimals and we get: 18,2142857 x 7 = 127,4999999. Down on our asses again.
This inflicts other fractions as well but here where 4 decimals makes it right, on other fractions this makes it wrong. The rounding makes it fokked.
So if I want it accurate, I think the way to go is via multiply table and do a 16by8-bit division which retains the accuracy better...
Or maybee I should just go take a caiphirinha and chill 8-D
|
| |
WVL
Registered: Mar 2002
Posts: 902 |
hehe, accuracy bites you in the ass :)
Have you thought about using logarithms or exponentials for your calculation? Normally these kill your resolution, but sometimes they help out wonderfully because with them you can have a changing accuracy, depending on the values you're working on..
let's say your denominator is very big (100-128 or something), then your calculation is a*128/demon. -> 128/denom is very close to 1, so a good resolution for big denominators, even with just 8 bit numbers.
Now, if your demoninator is very small, you're in trouble.
Anyway, think about doing the calc with exp or log, and see how that changes things :) |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: Alright, thanx, I see that we are more or less on about the same thing :-)
However I have an issue with accuracy which I want to flag:
Let's say you have the fraction 7/14 which you want to scale to x/255.
Calculating it directly it gives us x = 128 (rounded).
If we use a lookup table with 2 decimals we will get:
255/14 = 18,21
If we then multiply this with 7 we get the new numerator = 127,47 which unfortunately rounds to 127.
If we increase the amounts of decimals in our lookup table (8 bits is getting awfully small right about now) to 3 bits we get:
255/14 = 18,214
multiply with the numerator: 18,214 * 7 = 127,498 still not good enough.
So let's go crazy and do 4 decimals:
255/14 = 18,2143 (Rounded)
which gives: 18,2143 * 7 = 127,5001 and we finally got it right, right?
let's increase the accuract to 7 decimals and we get: 18,2142857 x 7 = 127,4999999. Down on our asses again.
This inflicts other fractions as well but here where 4 decimals makes it right, on other fractions this makes it wrong. The rounding makes it fokked.
So if I want it accurate, I think the way to go is via multiply table and do a 16by8-bit division which retains the accuracy better...
Or maybee I should just go take a caiphirinha and chill 8-D
Well. I said you should use 16-bit 8.8 fix point tables! Hence:
round(65535/14) = 4681
4681 * 7 = 32767 in 8.8 fix point (0x7fff) or with decimal point: 7f.ff
As you see, to properly round this value to eight bits you simply add 0.5 (0x80) => 7fff + 0x80 = 0x807f and truncate the top 8-bits (0x80).
Volia? |
| |
TWW
Registered: Jul 2009
Posts: 545 |
Alright, back from my cachasa haze...
Thanks Andreas for clearing that up for me. I think I have what I need.
WVL: Thqanks for the idea, but I need full accuracy along the whole scale 8-D |
| |
WVL
Registered: Mar 2002
Posts: 902 |
No you don't :D
Well, what i mean is that the accuracy that you need depends on the numbers in the calculation. So a 'sliding' accuracy might be very good (or rather good enough) in this case. |
| |
TWW
Registered: Jul 2009
Posts: 545 |
Quote: No you don't :D
Well, what i mean is that the accuracy that you need depends on the numbers in the calculation. So a 'sliding' accuracy might be very good (or rather good enough) in this case.
I see your point.
I'll investigate this a little more later. cheers! |
| |
TWW
Registered: Jul 2009
Posts: 545 |
So I finally found some tmie to finalize this stuff now when we're all global crisis'ing and all;
I've utilized jackassers extreemely fast multiplier along With the principles discussed above and it came out like this:
// Calculate Pixel Error - Steep slopes
// Y = DeltaY
// X = DeltaX
lda FractionTableLo,y
sta !SMC1++1
sta !SMC3++1
eor #$ff
sta !SMC2++1
sta !SMC4++1
lda FractionTableHi,y
sta !SMC5++1
eor #$ff
sta !SMC6++1
!SMC1:
lda Square1Lo,x
sec
!SMC2:
sbc Square2Lo,x
!SMC3:
lda Square1Hi,x
!SMC4:
sbc Square2Hi,x
clc
!SMC5:
adc Square1Lo,x
sec
!SMC6:
sbc Square2Lo,x
// A = Pixel Error
Tables:
.align $100
.pc = * "Math Tables"
FractionTableHi:
.fill 256, >round(65536 / i) + 0.5
FractionTableLo:
.fill 256, <round(65536 / i) + 0.5
Square1Lo:
.fill 512, [i*i/4] & $ff
Square1Hi:
.fill 512, [i*i/4] >> 8
Square2Lo:
.fill 512, [[[i-255]*[i-255]]/4] & $ff
Square2Hi:
.fill 512, [[[i-255]*[i-255]]/4] >> 8
I like it even thoug it introduces some degree overhead and eats some memory.
EDIT: i use it for hires, 256 pixels wide. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Four years later?! :D Haha, nice TWW! :D |
| |
Digger
Registered: Mar 2005
Posts: 437 |
No laugh JackAsser, I've been working on shit for 6 years and still have those "aha!" moments ;-) |
| |
TWW
Registered: Jul 2009
Posts: 545 |
hehe I see clarifications are in order.
If You see Post #7 I solved this ages ago using 8k tables but was Limited to DX/DY max 128.
If You see in my last post it's now for bitmap hires (256 pixels in X) which would add more tables so I figgured I'd try this way now as my line-algo is more mem-intensive.
I am still not sure if this is the best way to solve it though... |
| Previous - 1 | 2 | 3 - Next |
