View Single Post
Old 07-24-2009, 12:55 PM   #15
liteon
Human being with feelings
 
liteon's Avatar
 
Join Date: Apr 2008
Posts: 510
Default using lookup tables

for expensive functions, lookup tables (lut) can be used, so that the values are pre-computed in indexes (@init section) and only certain indexes are called in realtime (@sample section). results from using lut - are great accuracy and fast execution times.

here is an example with the log() function:

Code:
@init
//set depth of 256 indexes
depth=2^8;
i=0;
loop(depth,
//add value
ln[i]=log(i/depth);
i+=1;
);
@sample
//possible x range in this case [0,1]
x=0.5;
//multiply input to depth.
x=ln[x*depth]; // <-- the fractional part is discarded by the compiler
some outputs for the above:
Code:

depth is: 256
---
input is: 0.1
>> call index: 25
>> log(x): -2.30258509299405
>> from lut: -2.32630161961136
---
input is: 0.5
>> call index: 128
>> log(x): -0.693147180559945
>> from lut: -0.693147180559945
---
input is: 1
>> call index: 256
>> log(x): 0
>> from lut: 0
performance:

- in the form of:
Code:
x=0.5;
y=x;
y*=depth;
loop(100,
y=ln[y];
);
cpu usage is 35%
compared to 57% for 100 calls of x=log(x)

notes:
- bigger accuracy is achieved with bigger scaling factor 'depth' (and more indexes accordingly).
- if not enough accuracy - lower index is returned. example:
Code:

depth is: 256
---
input is: 0.01
>> call index: 2
>> log(x): -4.60517018598809
>> from lut: -4.85203026391962
---
input is: 0.001
>> call index: 0
>> log(x): -6.90775527898214
>> from lut: -Infinity
- a simple modification is required for negative inputs values (as there are no negative indexes) or different ranges other than [0,1]. in the case of ln[] negative indexes will return 0, which is acceptable.
- this method can be used for many functions, such as exp(), rand(), sin(), b^x and etcetera.



---
lubomir

Last edited by liteon; 08-22-2009 at 04:17 PM.
liteon is offline   Reply With Quote