| |
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 |
Well to tel lthe truth it's any combination of numbers between 1/1 -> 127/127 which get's scaled into xx/255.
There is no pattern or easy way to predict the next fraction unless I make a seperate routine for all the calculations (which will suck mem). |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: Well to tel lthe truth it's any combination of numbers between 1/1 -> 127/127 which get's scaled into xx/255.
There is no pattern or easy way to predict the next fraction unless I make a seperate routine for all the calculations (which will suck mem).
numerator´ = numerator * table[denominator]
A 8.8 fixpoint table with 128 entries should be sufficient.
table[x] = round((128/x)*256)
Then use this http://codebase64.org/doku.php?id=base:seriously_fast_multiplic.. to multiply fast. |
| |
TWW
Registered: Jul 2009
Posts: 545 |
Quote: numerator´ = numerator * table[denominator]
A 8.8 fixpoint table with 128 entries should be sufficient.
table[x] = round((128/x)*256)
Then use this http://codebase64.org/doku.php?id=base:seriously_fast_multiplic.. to multiply fast.
I'm trying to wrap my head around your post.
If the original denuminator is say 10 then calculating:
table[10] = round((128/10)*256) = 3277
If we then put this into:
numerator' = round(numerator * table[denominator]);0 // 0 decimals
I don't see how this gives the new numinator? I think I must have missunderstood you here.
I did some calculations and found that:
table[x] = round(256/denominator);3 // 3 decimals
then:
numerator' = numerator * table[x]
will give an accurate result. Looks like we're not getting around the 16 bits when doing the FP multiplication though. what will that do to the mult. tables? |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: I'm trying to wrap my head around your post.
If the original denuminator is say 10 then calculating:
table[10] = round((128/10)*256) = 3277
If we then put this into:
numerator' = round(numerator * table[denominator]);0 // 0 decimals
I don't see how this gives the new numinator? I think I must have missunderstood you here.
I did some calculations and found that:
table[x] = round(256/denominator);3 // 3 decimals
then:
numerator' = numerator * table[x]
will give an accurate result. Looks like we're not getting around the 16 bits when doing the FP multiplication though. what will that do to the mult. tables?
You said:
Quote:
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.
Hence 61 is found by calculating numerator*128/denominator
Basically you multiply by 1/x (in your case 128/x because you need that scale) which is same as dividing by x in the first place.
Regarding 16-bit multiplications using square sum tables, no problems, check out the wiki article.
/Andreas
|
| |
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! |
| Previous - 1 | 2 | 3 - Next |
