Re: Simplify formula for iterative programming

Stef wrote:

> 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 = Si (Sj ( sqrt [ (Ai - Aj)² + (Bi - Bj)² ] ) )
>
> where:
> A, B = two vectors (with numerical data) of length n
> Si = summation over i (= 0 to n)
> Sj = summation over j (= 0 to n)
>
> n is not fixed, but it changes with every run for my program.
> Therefore for I am looking for a simplication of H in order to
> calculate it when my A and B get extendend by 1 element (n = n +
> 1).

The standard deviation formula you mentioned is very simply derived
by expanding the binomial formula and summing terms. No similar thing
can be done in your case since the sqrt is inside the sums. So I
think the best you can do is split the sums as given at index n-1,
then note that the extension sums are the same except for length and
that their difference vanishes:

H[n]
= H[n-1] + sum{i=0..n-1, sqrt((A[i]-A[n])^2 + (B[i]-B[n])^2)}
+ sum{j=0..n , sqrt((A[n]-A[j])^2 + (B[n]-B[j])^2)}
= H[n-1] + 2 * sum{i=0..n-1, sqrt((A[i]-A[n])^2 + (B[i]-B[n])^2)}

The recursion starts out with H[0] = 0. Of course, more is possible
if you can elide the sqrt from the definition of H and reformulate
the rest of your algorithm accordingly.

--
Quidquid latine dictum sit, altum viditur.
.

Relevant Pages

  • Re: Simplification of complex expression
    ... >there exist a formula for simplification of this expression? ... which I'll do for now defining that Sqrt[] is ... If the sum of the two arguments of the factors on the ...
    (sci.math)
  • Re: Simplification of complex expression
    ... >>there exist a formula for simplification of this expression? ... which I'll do for now defining that Sqrt[] is ... > now the sum of the arguments is the argument of the product, ...
    (sci.math)