package octez-libs

  1. Overview
  2. Docs
package octez-libs
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module type Polynomial.UNIVARIATESource

Sourcetype scalar

The type of the polynomial coefficients. Can be a field or more generally a ring. For the moment, it is restricted to prime fields.

Sourcetype t

Represents a polynomial

Sourceval zero : t

Returns the polynomial P(X) = 0

Sourceval one : t

Returns the polynomial P(X) = 1

Returns the degree of the polynomial

Sourceval degree_int : t -> int
Sourceval have_same_degree : t -> t -> bool

have_same_degree P Q returns true if P and Q have the same degree

Sourceval get_dense_polynomial_coefficients : t -> scalar list

get_dense_polynomial_coefficients P returns the list of the coefficients of P, including the null coefficients, in decreasing order i.e. if P(X) = a_{0} + a_{1} X + ... + a_{n - 1} X^{n - 1}, the function will return a_{n - 1}, ..., a_{0}

Sourceval get_dense_polynomial_coefficients_with_degree : t -> (scalar * int) list

get_dense_polynomial_coefficients_with_degree P returns the list of the coefficients of P with the degree as a tuple, including the null coefficients, in decreasing order i.e. if P(X) = a_{0} + a_{1} X + ... + a_{n - 1} X^{n - 1}, the function will return (a_{n - 1}, n -1), ..., (a_{0}, 0).

Sourceval get_list_coefficients : t -> (scalar * int) list

get_list_coefficients P returns (a_4,4), (a_2,2), (a_0,0) if P = a_4 X^4 + a_2 X^2 + a_0

Sourceval evaluation : t -> scalar -> scalar

evaluation P s computes P(s). Use Horner's method in O(n).

Sourceval constants : scalar -> t

constants s returns the constant polynomial P(X) = s

Sourceval add : t -> t -> t

add P Q returns P(X) + Q(X)

Sourceval sub : t -> t -> t

sub P Q returns P(X) - Q(X)

Sourceval mult_by_scalar : scalar -> t -> t

mult_by_scalar s P returns s*P(X)

Sourceval is_null : t -> bool

is_null P returns true iff P(X) = 0

Sourceval is_constant : t -> bool

is_constant P returns true iff P(X) = s for s scalar

Sourceval opposite : t -> t

opposite P returns -P(X)

Sourceval equal : t -> t -> bool

equal P Q returns true iff P(X) = Q(X) on S

Sourceval of_coefficients : (scalar * int) list -> t

of_coefficients [(x_0, y_0) ; (x_1, y_1); ... ; (x_n ; y_n)] builds the polynomial Σ(a_i * X^i) as a type t.

By default, the null coefficients will be removed as the internal representation of polynomials is sparsed. However, a version with null coefficients can be generated if required. It is not recommended to use this possibility as it breaks an invariant of the type t.

Sourceval lagrange_interpolation : (scalar * scalar) list -> t

lagrange_interpolation [(x_0, y_0) ; (x_1, y_1); ... ; (x_n ; y_n)] builds the unique polynomial P of degre n such that P(x_i) = y_i for i = 0...n using the intermediate lagrange polynomials. lagrange_interpolation_fft can be used in case of a FFT friendly scalar structure. It is supposed all x_i are different.

Sourceval even_polynomial : t -> t

even_polynomial P returns the polynomial P_even containing only the even coefficients of P

Sourceval odd_polynomial : t -> t

odd_polynomial P returns the polynomial P_odd containing only the odd coefficients of P

Sourceval evaluation_fft : domain:scalar array -> t -> scalar list

evaluate_fft_imperative ~domain P evaluates P on the points given in the domain. The domain should be of the form g^{i} where g is a principal root of unity. If the domain is of size n, g must be a n-th principal root of unity. The degree of P can be smaller than the domain size. Larger polynomials can also be used but the implementation is not the most memory efficient yet and must be improved. The complexity is in O(n log(m)) where n is the domain size and m the degree of the polynomial. When m is smaller than n, the polynomial is padded with zeroes to reach n coefficients. The resulting list contains the evaluation points P(1), P(w), ..., P(w^{n - 1}).

Sourceval generate_random_polynomial : natural_with_infinity -> t

generate_random_polynomial n returns a random polynomial of degree n

Sourceval get_highest_coefficient : t -> scalar

get_highest_coefficient P where P(X) = a_n X^n + ... a_0 returns a_n

Sourceval interpolation_fft : domain:scalar array -> scalar list -> t

interpolation_fft ~domain [y_{0} ; y_{1} ; ... y_{n}] computes the interpolation at the points y_{0}, ..., y_{n} using FFT Cookey Tukey. The domain should be of the form g^{i} where g is a principal root of unity. If the domain is of size n, g must be a n-th principal root of unity. The domain size must be exactly the same than the number of points. The complexity is O(n log(n)) where n is the domain size.

Sourceval polynomial_multiplication : t -> t -> t

polynomial_multiplication P Q computes the product P(X).Q(X)

Sourceval polynomial_multiplication_fft : domain:scalar array -> t -> t -> t

polynomial_multiplication_fft ~domain P Q computes the product P(X).Q(X) using FFT. The domain should be of the form g^{i} where g is a principal root of unity. If the domain is of size n, g must be a n-th principal root of unity. The degrees of P and Q can be different. The only condition is degree P + degree Q should be smaller or equal to n - 2 (i.e. the domain should be big enough to compute n - 1 points of P * Q).

Sourceval euclidian_division_opt : t -> t -> (t * t) option
Sourceval extended_euclide : t -> t -> t * t * t

extended_euclide P S returns (GCD, U, V) the greatest common divisor of P and S and the Bezout's coefficient: U P + V S = GCD and GCD greatest coefficient is one

Sourceval (=) : t -> t -> bool

Infix operator for equal

Sourceval (+) : t -> t -> t

Infix operator for add

Sourceval (*) : t -> t -> t

Infix operator for polynomial_multiplication

Sourceval (-) : t -> t -> t

Infix operator for sub

Sourceval to_string : t -> string
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct