Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
 Welcome to our latest new user maak ! (Registered 2024-04-18) You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Fractional Scaling - Math problem
2012-02-05 08:06
TWW

Registered: Jul 2009
Posts: 541
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....
 
2012-02-08 20:50
TWW

Registered: Jul 2009
Posts: 541
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

2012-02-08 20:57
WVL

Registered: Mar 2002
Posts: 885
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 :)
2012-02-08 21:13
JackAsser

Registered: Jun 2002
Posts: 1987
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?
2012-02-10 03:39
TWW

Registered: Jul 2009
Posts: 541
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
2012-02-10 18:21
WVL

Registered: Mar 2002
Posts: 885
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.
2012-02-10 22:35
TWW

Registered: Jul 2009
Posts: 541
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!
2016-03-27 18:05
TWW

Registered: Jul 2009
Posts: 541
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.
2016-03-28 08:32
JackAsser

Registered: Jun 2002
Posts: 1987
Four years later?! :D Haha, nice TWW! :D
2016-03-29 18:44
Digger

Registered: Mar 2005
Posts: 421
No laugh JackAsser, I've been working on shit for 6 years and still have those "aha!" moments ;-)
2016-03-29 19:13
TWW

Registered: Jul 2009
Posts: 541
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
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
St0rmfr0nt/Quantum
maak
Bitbreaker/Performers
Isildur/Samar
kbs/Pht/Lxt
aeeben
Guests online: 125
Top Demos
1 Next Level  (9.8)
2 Mojo  (9.7)
3 Coma Light 13  (9.7)
4 Edge of Disgrace  (9.6)
5 Comaland 100%  (9.6)
6 No Bounds  (9.6)
7 Uncensored  (9.6)
8 Wonderland XIV  (9.6)
9 The Ghost  (9.6)
10 Bromance  (9.6)
Top onefile Demos
1 It's More Fun to Com..  (9.9)
2 Party Elk 2  (9.7)
3 Cubic Dream  (9.6)
4 Copper Booze  (9.5)
5 Rainbow Connection  (9.5)
6 TRSAC, Gabber & Pebe..  (9.5)
7 Onscreen 5k  (9.5)
8 Dawnfall V1.1  (9.5)
9 Quadrants  (9.5)
10 Daah, Those Acid Pil..  (9.5)
Top Groups
1 Oxyron  (9.3)
2 Nostalgia  (9.3)
3 Booze Design  (9.3)
4 Censor Design  (9.3)
5 Crest  (9.3)
Top Diskmag Editors
1 Jazzcat  (9.4)
2 Magic  (9.4)
3 hedning  (9.2)
4 Newscopy  (9.1)
5 Elwix  (9.1)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.049 sec.