Evaluating a particular polynomial efficiently?

Revision en1, by hliu1alt, 2023-02-23 12:40:59

I am working on a problem which I believe I have reduced to the following. I know that there's a better solution to this problem but I wanted to see if there's any interesting solution to find in this direction.

I have the following matrix

A = 
[
 1  1  1  1  1 ... 
 1  2  3  4  5 ...
 1  3  6 10 15 ...
 1  4 10 20 35 ...
 1  5 15 35 70 ...
 ...
]

Notice that A[i][j] = A[i-1][j] + A[i][j-1] and that the diagonals form binomial coefficient patterns.

I want to evaluate the following function in better than O(n) time.

f(i,j,x) = (A[i][0] * x + A[i][1] * x^2 + A[i][2] * x^3 + ... + A[i][n] * x^n) % bigPrime

If it helps, there are a fixed, very small, number of values of x for which I will ever need to evaluate this at.

For example, say x is only ever in {1, 2, 3}.

Is this possible?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English hliu1alt 2023-02-23 12:41:45 2 Tiny change: '.\n\n`f(i,j,x) = (A[i' -> '.\n\n`f(i,n,x) = (A[i'
en1 English hliu1alt 2023-02-23 12:40:59 881 Initial revision (published)