extremly quick ways to calculate

[DrAgon]

The aim of this section is to offer code-snippets, that allow the user
to handle math-operations that are hopefully 100 times quicker then
the usual math.builtin-functions of Thyme, and they all will be
made with allready existing Thyme-functions of simpler kind.

Why do you need such super-quick operations? Algodoo is allready so
quick like lightning!
a) If you want to implement a very large number of objects for example
to simulate physical states with more then 1000 particles, which
can happen in thermodynamic models of reality.
b) If you want to let particles interact in other ways then just
collide or interact by gravity. Here i have specially in mind to
add potential-functions of all kind, so i can e.g. implement
electrical forces IN ADDITION to gravity. No other software exists
at moment that allows this for reasonable price, and Algodoo is
affordable for every pupil.

For example i will add here a
square-root function that linear-interpolates the values for the
square-root, by using an array of pre-calculated values. This array
contains 101 entries.

In addition we can compare the math.builtin-funktions
and the new functions, e.g. a calculation of 1000 repetitions will
yield the time that needed, wich is displayed then in the console.

If you want to contribute to these ideas, i would be glad.
Thanks to Kilinich, he allready gave me a lesson, and also
to one of my pupil (JPM), who gave me the array needed.

In two code-snippets i'll add
a) the array and after that
b) the way how to get the quick sqareroot of rr, giving sqrres.
In that section i also explain how the linear interpolation
works and which variables are used for which purpose,
by giving an example. After that, i display
c) the tests of accuracy in various ranges.


To a) So here is the array, that is needed:

Code: Select all

Scene.my.SqrtArray100 = [
0.0,
0.1,
0.14142136,
0.17320508,
0.2,
0.2236068,
0.24494897,
0.26457513,
0.28284271,
0.3,
0.31622777,
0.33166248,
0.34641016,
0.36055513,
0.37416574,
0.38729833,
0.4,
0.41231056,
0.42426407,
0.43588989,
0.4472136,
0.45825757,
0.46904158,
0.47958315,
0.48989795,
0.5,
0.50990195,
0.51961524,
0.52915026,
0.53851648,
0.54772256,
0.55677644,
0.56568542,
0.57445626,
0.58309519,
0.59160798,
0.6,
0.60827625,
0.6164414,
0.6244998,
0.63245553,
0.64031242,
0.64807407,
0.65574385,
0.66332496,
0.67082039,
0.678233,
0.68556546,
0.69282032,
0.7,
0.70710678,
0.71414284,
0.72111026,
0.72801099,
0.73484692,
0.74161985,
0.74833148,
0.75498344,
0.76157731,
0.76811457,
0.77459667,
0.78102497,
0.78740079,
0.79372539,
0.8,
0.80622577,
0.81240384,
0.81853528,
0.82462113,
0.83066239,
0.83666003,
0.84261498,
0.84852814,
0.85440037,
0.86023253,
0.8660254,
0.87177979,
0.87749644,
0.88317609,
0.88881944,
0.89442719,
0.9,
0.90553851,
0.91104336,
0.91651514,
0.92195445,
0.92736185,
0.93273791,
0.93808315,
0.94339811,
0.9486833,
0.9539392,
0.9591663,
0.96436508,
0.96953597,
0.97467943,
0.9797959,
0.98488578,
0.98994949,
0.99498744,
1.0];

To b)
How does linear interpolation work with this array? Look at this example:
Task: take the squareroot of rr in a quick way by usage of a precalculated array of
values and interpolate linear between them. For this, the value of r is
moved into the range of 0 and 1, giving rnew, the result will be in sqrres.

Example: rr=6.89 . Divide this by 100 gives rnew=0.0689. To scale back, one has to multiply
later on with the squareroot of 100, which is 10. Now take the values of 0.06 and 0.07 from
of the array, it is the array(6) and the array(7), and the number 6 you get from
taking the integer-part of 100*rnew. 7 is 6+1. For our case we have
a=array(6)=0.24494897, and b=array(7)=0.26457513. Linear interpolated this gives
the (a+0.89*(b-a)), which is 0.2624162. The 0.89 you get by 100*rrest,
where rrest=rnew-n1*0.01. Multiplying with 10 to scale back, this gives
the squareroot-result sqrres=2.624162 , which is accurate enough to do simulation physics
with it ( the exact result is about 2,624881 ).
Other variables are rnew,n1,n2,rrest and the result sqrres.

Code: Select all

Scene.my.makerrrange = rr<0.01 ? {   rnew=rr*100.0;
                                     n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=0.1*(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));
             } :
{ Scene.my.makerrrange = rr < 1.0 ? {   rnew=rr;
               n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));
                                  } : 
   { Scene.my.makerrrange = rr < 100.0 ? {rnew=rr/100.0;   
               n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=10.0*(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));
                 } : 
     { Scene.my.makerrrange = rr < 10000.0 ? {rnew=rr/10000.0;
               n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=100.0*(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));   
                } : {sqrres=rr^0.5;}
     }
   }
}

To c) the tests of accuracy in various ranges:
first number is rr, we want to get squareroot of rr.
second number is the exact squareroot by rr^0.5 and
third number below the second is the result yielded by the quicksquareroot.

0.00235____0.0484767
___________0.0484740

0.34567____0.587937
___________0.587922

5.493 ______2.343715
___________2.341285

7399_______86.01744
___________86.01743

750________27.38612
___________27.37089

88888______298.1409
___________298.1409 but is not quicker in that case, as for
numbers>10000 the built-in sqrt function is used.

Summary: I am very content with the accuracy. Next to be tested is the
time that is used for 100000 calculations via rr^0.5
versus the same amount of calculations via the quick method.

[Kilinich]

Good idea but I don't see implementation... where is scene.my.sqrt(x) function to test?

[DrAgon]

First thing to do is to copy and paste the array Scene.my.SqrtArray100
from the code snippet in a) , which you can select by klicking on the
blue written SELECT ALL, then right-click on the selected code, klick on
"copy" . Then press F10 to open the Console in Algodoo, and paste the
array there.

After that, you have to copy the following function, lets call it
Scene.my.sqrtquick, by the same procedure and paste it into
the Console of Algodoo.

Code: Select all

Scene.my.sqrtquick = (rr)=>{
Scene.my.makerrrange = rr<0.01 ? {   rnew=rr*100;
                                     n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=0.1*(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));
             } :
{ Scene.my.makerrrange = rr < 1.0 ? {   rnew=rr;
               n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));
                                  } : 
   { Scene.my.makerrrange = rr < 100.0 ? {rnew=rr/100.0;   
               n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=10.0*(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));
                 } : 
     { Scene.my.makerrrange = rr < 10000.0 ? {rnew=rr/10000.0;
               n1=math.toInt(100*rnew);
               n2=n1+1;
               rrest=rnew-n1*0.01;
   sqrres=100.0*(Scene.my.SqrtArray100(n1)+100*rrest*(Scene.my.SqrtArray100(n2)-Scene.my.SqrtArray100(n1)));   
                } : {sqrres=rr^0.5;}
     }
   }
}
}

After that, you can use the function e.g. if you type in the console
Scene.my.sqrtquick(750)
then you get the result 27.37089, or if you type
Scene.my.sqrtquick(0.632)
you get the result 0.794980, which is not too far away from the exact 0.794984.

I dont want to implement the whole array into this function, as it would take time to
define its array-values over and over whenever the function is called.
So i think its best to maintain these two steps.
I hope this code saves more time calculating squareroots then i used for its coding,
but if one uses 1000 particles, one complete interaction would need
1000*1001/2=500500 interactions of each particle with each other, and each of them
would need a squareroot-calculation.

[Xray]

I'm not a math wiz like some of you guys are, so I may not understand this thread as well as some, but I question if using the simple sqrt function x^0.5 is really slower than requiring Algodoo to interpret all that code in your linear interpolation algorithm. Please explain.

[jon_joy_1999]

this is the classic time–memory tradeoff scenario, where computation time is reduced (because the data is already calculated) but memory is increased because each data has to be stored in the table

edit: more information

what he has here are the square roots between 0 and 1 in 0.01 increments. so if you wanted to know the square root of say 0.34, you would grab the 35th* number in the table, which is 0.58309519
compared to my calculator which says sqrt(0.34) = 0.58309518948453004708741528775456
now, for a human it is cognitively easier to type sqrt()0.34 into their calculator, than to count through 35 numbers to get the right one, but a computer can do it in maybe 2 operations:

Code: Select all

GOTO INDEX
READ FLOAT

(psuedocode, not ready for prime time)
versus something like
short isqrt(short num) {
short res = 0;
short bit = 1 << 14; // The second-to-top bit is set: 1L<<30 for long

// "bit" starts at the highest power of four <= the argument.
while (bit > num)
bit >>=2;

while (bit != 0) {
if (num >= res + bit) {
num -= res + bit;
res = (res >> 1) + bit;
}
else
res >>= 1;
bit >>= 2;
}
return res;
}

from Methods of computing square roots -Binary numeral system
which incidentally has a link back to my first link hehe

*add 1, because 0 is calculated; or you could consider the table as zero indexed

[Xray]

Jon_joy -- Thanks very much for that excellent explanation. I did learn the benefits of look-up tables way back when I worked as an assembler language programmer for the Intel 8085 uP. Software ran lightning fast when using tables compared to calling functions in a floating point software package (at the expense of more memory usage, as you had mentioned). I just didn't know if the same applied to Thyme script language. Thanks again!

[DrAgon]

Testresults: pittily my function is not faster.

I did tests now with the help fo Kilinichs xFor-function

Code: Select all

scene.my.xFor = (n1, n2, code) => {
  n2 > n1 ? {
    m := (n1 + n2) / 2;
    scene.my.xFor(n1, m, code);
    scene.my.xFor(m + 1, n2, code)
  } : {code(n1)}
}

and i performed 100000 repetitions of a calculation:

Code: Select all

nn=0.001;
print(nn);
scene.my.xFor(0,100000, (n) => {nn=nn+0.001; sq=nn^0.5});
print(nn);

results in:
0.001
2113759 ms: Console "print" cmd: 0.001
99.958694
2121138 ms: Console "print" cmd: 99.958694
which is 7.379 seconds.
and substituted then the ^0.5 command by my sqrtquick-function:

Code: Select all

nn=0.001;
print(nn);
scene.my.xFor(0,100000, (n) => {nn=nn+0.001; sq=Scene.my.sqrtquick(nn)});
print(nn);

results in:
0.001
2156497 ms: Console "print" cmd: 0.001
99.958694
2175630 ms: Console "print" cmd: 99.958694
which is 19.133 seconds.

Obviously the simple ^0.5 is much quicker.
I only see chances to improve the speed of the sqrtquick() function, if i can use
bit-shift-operations, or reduced precision-operators, that need less time in basic algebraic operations.
Do we have such operators or functions in thyme?
I saw a variable named "controllerAcc=11.0" which could have this meaning ( controller Accurarcy ? )
Anyway, it was interesting to read also your sqrt-calculation-method of wikipedia, thanks for that.

[Xray]

I saw a variable named "controllerAcc=11.0" which could have this meaning ( controller Accurarcy ? )

Controller Acceleration