CODEWITHSUNDEEP
algorithmsumproduct
jorgen
jorgen

Reputation: 3593

Finding an algorithm without divisions for multiple sum

I have a quantity e that is given by the following multiple sum and product:

enter image description here

where enter image description here and enter image description here are vectors and t = 0, 1, ... , N-1.

As an example, if N = 4 the quantities corresponding to i = 2 are

enter image description here

enter image description here

enter image description here

enter image description here

The elements of a and b can be arbitrarily small. Because of this I want to avoid divisions. The problem is that I can't for the life of me make an algorithm that computes this, even in the most straightforward way (although speed is an issue so I would like a fast one). Any pointers?

Upvotes: 1

Views: 63

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I think you can compute this in O(t.N) cycles using dynamic programming.

The idea is to compute a a quantity f(i,t,n) which is exactly the same as your e(i,t) except that the first sum has N replaced by n.

We define f(i,t,0) to be 1 if t==0, or 0 otherwise.

We can compute f(i,t,n) based on previous values by considering cases of whether the position at index n is to be "a", "b", or skipped.

If n==i
    f(i,t,n)=f(i,t,n-1)
else
    f(i,t,n)=f(i,t,n-1).a_n+f(i,t-1,n-1).b_n

The answer is given by e(i,t)=f(i,t,N).

We will compute intermediate values for each choice of t and n, so the overall complexity is O(tN).

For example,

f(2,0,1) = a_1
f(2,0,2) = a_1.a_2
f(2,0,3) = a_1.a_2.a_3
f(2,1,1) = b_1
f(2,1,2) = f(2,1,1).a_2 + f(2,0,1).b_2 = b_1.a_2+a_1.b_2

Upvotes: 1

Related Questions