Results of an iterative prefix sum

Question

An array of size s + 1 is initialized such that a[i] = i for 0 <= i < s , a[s] = 0. Then I iteratively use dynamic programming to sum the values of the array, going from largest to smallest, doing it t times. Results get large very quickly so I reduce them mod some modulus.

If s = 10, the arrays look like this:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

[0, 45, 44, 42, 39, 35, 30, 24, 17, 9, 0]

[0, 45, 89, 131, 170, 205, 235, 259, 276, 285, 0]

And so on.

After t iterations I am interested in the extreme non-zero values of the array. My algorithm does this explicitly, resulting in time complexity of O(s*t). Is there any algorithm that can produce either (or both) of these values in a better time complexity? Specifically I was thinking about whether matrix exponentiation is possible, reducing time complexity to O(s*log(t)), but really any approach is welcome as well as optimizations.

My code:

public class ArraySummation{

     public static void main(String []args)
     {
        int s = 10;
        long t = 10;
        
        long modulus = 1000000;
        
        long [] a = new long [s + 1];
        for (int i = 1 ; i < s ; i++)
            a[i] = i;

        for (int i = 2 ; i <= t ; i++)
        {
            if ((i & 1) == 1)
                for (int j = 1 ; j < a.length - 1 ; j++)
                {
                    a[j] += a[j - 1];
                    if (a[j] >= modulus)
                        a[j] -= modulus;
                }

            else
                for (int j = a.length - 2 ; j >= 1 ; j--)
                {
                    a[j] += a[j + 1];
                    if (a[j] >= modulus)
                        a[j] -= modulus;
                }
        }

        System.out.println(a[1]);
        System.out.println(a[s - 1]);
     }
}

user_5289186 · Answer

For s=10 it can be found in OEIS https://oeis.org/A030113 as a linear recurrence.

There is also a formula in matrix form for all s

(PARI) k=9; M(k)=matrix(k, k, i, j, if(1-sign(i+j-k), 0, 1)); v(k)=vector(k, i, 1); a(n)=vecmax(v(k)*M(k)^n)

Sample for the matrix construction

Matrix construction

Explanation The Matrix M operates by multiplication to Matrix T as follows to the result matrix R (short: M . T = R)

First column of R is the last column of T
Second column of R is the sum of the last and second last column of T
...
Last column of R is the sum of all columns of T

Thus the adding procedure of the question is done by matrix multiplication, but with initialization a[i] = 1. After first round with M^2 the last column contains the initialization of the question a[i] = i

M^2

Depending on the parameters s, t it could be better to use the matrix exponentiation like M^8 = M^4 . M^4 = M_4 . M_4 , M^4 = M^2 . M^2 = M_2 . M_2, where M_2 and M_4 can be reused. So instead of 8 matrix mulitiplications with only 3 multiplication we can get the result.

The complexity is O(s^2 * log(t))

Results of an iterative prefix sum

1 Answers