CODEWITHSUNDEEP
algorithmsequencereduce
Soggiorno
Soggiorno

Reputation: 774

Algorithm for reducing sequence into smaller sequence (for specific function)

I have a sequence of (X,Y) pairs: (X_0,Y_0)....(X_N,Y_N)

I add a new pair to the sequence at every time step, t

At some time in the distant future, t_n, I want to use a function to reduce the sequence into a number.

The function takes the sequence of pairs and an input Z:

f(Z) = ((1/X_0)-(1/Z))*Y_0 + ((1/X_1)-(1/Z))*Y_1 + ... + ((1/X_N)-(1/Z))*Y_N

My problem:

I don't want to store every pair of these sequences. This would require too much space.

I want to reduce the sequence into some kind of incremental representation that will allow me to

How do I go about doing this?

Upvotes: 1

Views: 58

Answers (1)

P. Dmitry
P. Dmitry

Reputation: 1121

f = 
  (1/X_0-1/Z)*Y_0 + (1/X_1-1/Z)*Y_1 = 
  (Y_0/X_0 - Y_0/Z) + (Y_1/X_1 - Y_1/Z) =
  Y_0/X_0 - Y_0/Z + Y_1/X_1 - Y_1/Z =
  Y_0/X_0 + Y_1/X_1 - Y_0/Z - Y_1/Z =
  (Y_0/X_0 + Y_1/X_1) - (Y_0 + Y_1) / Z = 
  A - B / Z

A = SUM(Y_i / X_i)
B = SUM(Y_i)

enter image description here

So you can incrementally update A and B and calculate the result in any moment of time

Upvotes: 3

Related Questions