# Algorithms

Definitions (1) (2) (3)

1. Incremental calculation of hk(x1, x2, …, xn), for increasing k, with O(n) increment step

 1 for i = 1 to n loop 2 wi ← 1 // wi = h0(x1, x2, …, xi) = 1 3 end loop 4 for k = 1 to … loop 5 w1 ← x1 w1 // w1 = hk(x1) = x1k 6 for i = 2 to n loop 7 wi ← wi − 1 + xi wi // wi = hk(x1, x2, …, xi) 8 end loop 9 output wn // wn = hk(x1, x2, …, xn) 10 end loop

2. Incremental calculation of hk(m1x1, m2x2, …, mnxn) — which may be useful when ∑ mi n

 1 y ← 1 // y = h0(m1 • x1, m2 • x2, …, mn • xn) = 1 2 for i = 1 to n loop 3 wi ← 0 4 end loop 5 for k = 1 to … loop 6 s ← 0 7 for i = 1 to n loop // O(n) loop 8 wi ← xi (wi + mi y) 9 s ← s + wi 10 end loop 11 y ← s / k // y = hk(m1 • x1, m2 • x2, …, mn • xn) 12 output y 13 end loop

The same algorithm may be useful when the mi are not integers (e.g., when calculating a convolution of gamma distributions with varying scale parameters). In this case the algorithm outputs for each k the value 3. Incremental calculation of φk(t; x1, x2, …, xn)

 1 for i = 0 to n loop 2 wi ← 1 // wi = φ0(t; x1, x2, …, xi) = 1 3 end loop 4 for k = 1 to … loop 5 w0 ← w0 t / k // w0 = φk(t; ~) = t k / k! 6 for i = 1 to n loop // O(n) loop 7 wi ← wi − 1 + xi wi // wi = φk(t; x1, x2, …, xi) 8 end loop 9 output wn // wn = φk(t; x1, x2, …, xn) 10 end loop

4. If G(s) is the rational function then the inverse Laplace transform of G(s) is the function where Ai, k is given by: If one modifies G(s) by incrementing mj for some 1 ≤ jn, then g(t) is replaced by (g Dμj)(t), and the coefficients Ai, k change as shown below:

 1 s ← 0 2 for i = 1 to n loop 3 if i ≠ j then 4 Ai, 0 ← Ai, 0 / (μj − μi) 5 for k = 1 to mi − 1 loop 6 Ai, k ← (Ai, k − Ai, k − 1) / (μj − μi) 7 end loop 8 s ← s + Ai, mi − 1 9 end if 10 end loop 11 Aj, mj ← −s // new coefficient 12 mj ← mj + 1

If j = n + 1 so that we are including a new factor (s + μn + 1) in the denominator of G(s), insert the line mj ← 0 before line 1 and append the line nn + 1 after line 12.

If the value of g(t) is needed only for a specific value of t, and if it is known that one mj will be incremented repeatedly and no other mi will increase, then a different version of the algorithm can be used to recalculate Ai, k only for ij, without accumulating the sum s. The sum of all the Aj, k terms can be recalculated at each iteration using the φ function above without calculating the individual coefficients Aj, k.

Note: Given any function g(t) of the form with arbitrary coefficients Ai, k, if we wish to calculate (g Dμj)(t), the same algorithm for updating the coefficients works. However, the shortcut method of evaluating g(t) using the φ function is not guaranteed to work for arbitrary Ai, k.