| |
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....
|
| |
WVL
Registered: Mar 2002
Posts: 902 |
Maybe you're looking at it the wrong way, being too fixed at this scaling problem. Maybe there's another way to do your calculation, skipping this problem.
It helps if we'd know what you're trying to do :) |
| |
TWW
Registered: Jul 2009
Posts: 545 |
~8K table was what I needed and a little indexed magic. an ok comprimise between speed and memory.
I can't tell you what it's for coz that will ruin the surprise no 8-) |
| |
chatGPZ
Registered: Dec 2001
Posts: 11386 |
i have abused the table-of-squares multiplikation idea to scale a number in 0-127 range.... (this) instead of using (x^2)/4 simply use (x^2)/2 for the table(s). then the highbyte of the result is your scaled value. seems slightly slower than with an 8k table, but uses much less memory :) (this would actually be an 1.7 fixedpoint multiplication) |
| |
WVL
Registered: Mar 2002
Posts: 902 |
does your demoninator change a lot? or is it fixed for say a whole frame? I gots me an idea.. |
| |
TWW
Registered: Jul 2009
Posts: 545 |
Well.. It changes and it's async. to the frame but what did you have in mind? |
| |
WVL
Registered: Mar 2002
Posts: 902 |
Well, i remembered a routine i wrote in arcanum, it also kinda scales fractions, but not quite. I think it would maybe work if the scaling factor doesnt change a lot.
So, how often (after how many scalings) does the scaling factor (original demoninator) change? |
| |
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
|
| Previous - 1 | 2 | 3 - Next |
