Module interp 

Incremental interpolation.

Newton for polynomials, Thiele for rational functions, and the Berlekamp-Massey and transposed Vandermonde steps of sparse interpolation. Each grows one point at a time and reports when a new point was already predicted, so no degree bounds are needed.

Structs

Massey

Berlekamp-Massey, one term at a time: the shortest linear recurrence generating a sequence.

Newton

Newton’s divided differences at distinct abscissae.

Thiele

Thiele’s continued fraction c_0 + (t - t_0) / (c_1 + (t - t_1) / (c_2 + ...)).

Functions

master

prod_l (z - v_l).

solve

Solves the transposed Vandermonde system sum_l c_l v_l^(j+1) = w_j.