|
D.4.9.2 polyInterpolation
Procedure from library ffmodstd.lib (see ffmodstd_lib).
- Usage:
- polyInterpolation(d, e[, n, L]); d list, e list, n int, L list
- Return:
- a list l_p where f:=l_p[1] is a polynomial of degree at most size(d)-1
which satisfies the conditions f(d[i])=e[i] for all i, l_p[2] is the product
of all (var(n)-d[i]) for 1 <= i <= size(d) and l_p[3]=d.
- Note:
- The procedure applies the Newton interpolation algorithm to the pair (d,e)
and returns the output w.r.t. the first variable (default) of the ground
ring. If an optional parameter n, 1<=n<=N (N is the number of variables in the
current basering), is given, then the procedure returns the list l_p w.r.t. the
n-th variable. Moreover, if the number of points (d'[i],e'[i]) is not large enough
to obtain the target polynomial, L = polyInterpolation(d', e', n) can be provided
as an optional parameter to add more interpolation points.
The elements in the first list must be distinct.
Example:
| LIB "ffmodstd.lib";
ring rr = 23,(x,y),dp;
list d = 1,2,3,4;
list e = -1,10,3,8;
polyInterpolation(d,e);
==> [1]:
==> 5x3+7x2+x+9
==> [2]:
==> x4-10x3-11x2-4x+1
==> [3]:
==> [1]:
==> 1
==> [2]:
==> 2
==> [3]:
==> 3
==> [4]:
==> 4
polyInterpolation(d,e,2)[1];
==> 5y3+7y2+y+9
list d1 = 5,6;
list e1 = -7,6;
list L = polyInterpolation(d,e);
L = polyInterpolation(d1,e1,1,L); // add points
L;
==> [1]:
==> 10x5-5x4+3x3+3x2-x-11
==> [2]:
==> x6+2x5-9x4+x3-9x2+7x+7
==> [3]:
==> [1]:
==> 1
==> [2]:
==> 2
==> [3]:
==> 3
==> [4]:
==> 4
==> [5]:
==> 5
==> [6]:
==> 6
ring R = (499,a),x,dp;
list d2 = 2,3a,5;
list e2 = (a-2), (9a2-8a), (a+10);
polyInterpolation(d2,e2);
==> [1]:
==> x2-3*x+(a)
==> [2]:
==> x3+(-3a-7)*x2+(21a+10)*x+(-30a)
==> [3]:
==> [1]:
==> 2
==> [2]:
==> (3a)
==> [3]:
==> 5
|
|