| |
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? |
| |
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! |
| |
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... |
