NewtonInterpolation
Implements Newtons interpolation algorithm. All calculations will be carried out by finite field algebra.
Value parameters
- prime
-
a prime number
- supportingPoints
-
some pairwise different supporting points
Attributes
- Constructor
-
Creates a new NewtonInterpolation by applying some supporting points and a prime number.
- Graph
-
- Supertypes
Members list
Value members
Concrete methods
Supporting points := (x(0), y(0)), ..., (x(n), y(n)).
Supporting points := (x(0), y(0)), ..., (x(n), y(n)).
Computes the newton coefficients c(n)...c(0) by dynamic programming.
y(n) - c(0) - c(1)*(x(n) - x(0)) - ... - c(n-1)*((x(n) - x(0))*...*(x(n) - x(n-2))
c(n) := ---------------------------------------------------------------------------------- (mod prime)
(x(n) - x(0))* ... *(x(n) - x(n-1))
y(1) - c(0)
c(1) := ----------- (mod prime)
x(1) - x(0)
c(0) := y(0) (mod prime)
Following applies: (n + 1) == number of supporting points. This gives a polynom of degree n with (n + 1) Newton coefficients.
Attributes
- Returns
-
the calculated newton coefficients
Returns the present tracer for this object.
Returns the present tracer for this object.
Attributes
- Returns
-
the current tracer, by default the NullTracer
- Definition Classes
Computes below expression.
Computes below expression.
(x(i) - x(0))*(x(i) - x(1))* ... *(x(i) - x(j)), i > j
Expressions of this form need to be evaluated during the calculation of the Newton coefficients.
Value parameters
- i
-
references the x-ccordinate of a supporting point (always in minuend position)
- j
-
denotes the upper index of the x-coordinates in subtrahend position
Attributes
- Returns
-
the value of the term (mod prime)
Returns a string representation of the object.
Returns a string representation of the object.
The default representation is platform dependent.
Attributes
- Returns
-
a string representation of the object.
- Definition Classes
-
Any
Inherited methods
Custom control structure for tracing of embraced code blocks.
Custom control structure for tracing of embraced code blocks.
Type parameters
- T
-
the actual type of the embraced code block
Value parameters
- block
-
the embraced code block
- callee
-
the call site
- method
-
denotes the method signature
- resultType
-
denotes the return type
Attributes
- Returns
-
returns whatever block returns
- Inherited from:
- Tracing
Concrete fields
n supporting points give a polynom of degree n - 1
n supporting points give a polynom of degree n - 1
Attributes
Creates lazily the NewtonPolynomial by computing the Newton Coefficients. For the definition of a NewtonPolynomial with degree n - 1 we need only n - 1 x values projected from the supporting points whereas n of them are needed for the computation of the coefficients.
Creates lazily the NewtonPolynomial by computing the Newton Coefficients. For the definition of a NewtonPolynomial with degree n - 1 we need only n - 1 x values projected from the supporting points whereas n of them are needed for the computation of the coefficients.