[R] Simplify iterative programming

Stefaan Lhermitte stefaan.lhermitte at biw.kuleuven.be
Fri Nov 4 10:28:23 CET 2005


Dear,

I am looking for the simplification of a formula to improve the
calculation speed of my program. Therefore I want to simplify the
following formula:

H = sum{i=0..n-1 ,  [ sum {j=0..m-1 ,  sqrt ( (Ai - Bj)^2 + (Ci -
Dj)^2) }  ]  }

where:
A, C = two vectors (with numerical data) of length n
B, D = two vectors (with numerical data) of length m
sqrt = square root
Ai = element of A with index i
Bj = element of B with index j
Ci = element of C with index i
Dj = element of C with index j

I am calculating H in a merging process so A, B will merge in step 2
into A' and C, D into C':
A' = {A,B} : vector of length (n+m)
C' = {C,D} : vector of length (n+m)

Then again I will calculate H with two new vectors X and Y (of length
p):
H = sum{i=0..n+m-1 ,  [ sum {j=0..p-1 ,  sqrt ( (A'i - Xj)^2 + (C'i -
Yj)^2) }  ]  }

These steps are iterated in a loop with always new vectors (e.g. X and
Y)

Now I'am looking for a simplication of H in order to avoid long
calculation time.
I know a computional simplified formula exists for the standard
deviation (sd) that is much easier in iterative programming. Therefore
I wondered I anybody knew about analog simplifications to simplify H:

sd = sqrt [ sum{i=0..n-1, (Xi - mean(X) )^2 ) /n } ]  -> simplified
computation
-> sqrt [  (n *  sum{i=0..n-1,  X^2 } ) - ( sum{i=0..n-1,  X } ^2 ) /
n^2 ]

This simplied formula is much easier in iterative programming, since I
don't have to keep every element of X .

For example if we want to calculate sd of A' with the vectors A and C:
sd(A')
= sqrt [  ((n+m) *  sum{i=0..n+m-1,  A'^2 } ) - ( sum{i=0..n+m-1,  A' }
^2 ) /  (n+m)^2 ]
= sqrt [  ((n+m)*  (sum{i=0..n,  A^2 } + sum{i=0..m,  C^2 } ) )
     - ( ( sum{i=0..n-1,  A } + sum{i=0..m-1,  C } )^2 ) /  (n+m)^2 ]

The advantage of this formula is, that I don't have to keep every value
of A and C to calculate sd(A'). I can do the following replacements:
sum{i=0..n,  A^2 } = A2
sum{i=0..m,  C^2 } = C2
sum{i=0..n-1,  A } = A3
sum{i=0..m-1,  C } = C3

So sd(A')=
  sqrt [  ( (n+m)*(A2+ C2) )  - ( (A3 + C3)^2 ) /  (n+m)^2 ]

In this way my computation intensive calculation is replaced by a
calculation of simple numbers.

Can anybody help me to do something comparable for H? Any other help to
calculate H easily in an iterative process is also welcome!

Kind regards,
Stef

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm




More information about the R-help mailing list