| |
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)? |
|
| |
ChristopherJam
Registered: Aug 2004
Posts: 1409 |
What you are asking for is a fixed-point division routine.
It depends somewhat on what range of input and output values you are expecting, and how much accuracy you want - if the inputs are eight bit, and the result always less than 255, I'd suggest perhaps using log and exp tables?
128*x/y=128*exp(log(x)-log(y))
=f[g[x]-g[y]]
You'll need to scale the log and exp tables such that g[x]-g[y] is between 0 and 255 (or range over 510 values if you add g[x] to 255-g[y] by using lda $ttyy,x) |
| |
Conrad
Registered: Nov 2006
Posts: 849 |
I'm playing around with line drawing code as well, but I'm very lame when it comes to getting accurate divisional results.
@TWW: Reading Krill's math articles from Attitude #11 is also a good suggestion, as he explains about an accurate base2 logarithm and exp tables that will give accurate division results. I'm still unsure how to thouroughly use it though. Basically I'm looking in the needs of the following pseudo code (just for X coordinate at the moment):
pixel_draw_loop
clc
x_f
lda #$00
adc #(fraction quotient)
sta x_f+1
x_
lda #$00
adc #(whole quotient)
sta x_+1
... then use (x_) for lookup tables on pixel drawing etc.
So, how do you extend the log/exp table method to lookup on both whole and fractional quotient, using a whole divisor and dividend? 16-bit lookups? |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1409 |
Yes, I just have two separate tables for the low and high bytes of the results.
The case that has me really stumped is an efficient and accurate X*Y/Z, all operands 16 bits wide. I use it for the frustum clipping in camera space for the 3d renderer in the final part of Effluvium, and my code for that is slooow. |
| |
TWW
Registered: Jul 2009
Posts: 545 |
If I sacrifice aprox. 8k for a table I can freely scale any denuminator from 1-127 up to 127 and find the rounded nominator scaled up.
ldy old_denuminator
lda old_numinator
asl
tax
lda tabindex,x
sta $fc
lda tabindex+1,x
sta $fb
lda ($fb),y
However I'm not happy about the amont of memory spent on that table :-)
I can use a 16 bit lookup table for n*256 (512 bytes and n is the old nominator) the use a log/exp division to divide the result with the old denuminator to get the new nominator. This requires more tables though but should be cheeper on mem then the solution above. Timewise, I figgure it wouldn't differ much. but I am unsure of the accuracy though. Bitwise div is out of the question. |
| |
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? |
... 14 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 | 3 - Next |
