package octez-libs

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

Parameters

Signature

include Octez_bls12_381_polynomial.Evaluations_sig with type scalar = E.scalar with type domain = E.domain with type polynomial = E.polynomial with type t = E.t
type scalar = E.scalar
type polynomial = E.polynomial
type t = E.t
val t : t Repr.t
val init : int -> (int -> scalar) -> degree:int -> t

init size f degree initializes an evaluation of a polynomial of the given degree.

val of_array : (int * scalar array) -> t

of_array (d, e) creates a value of type t from the evaluation representation of a polynomial e of degree d, i.e, it converts an OCaml array to a C array

val to_array : t -> scalar array

to_array converts a C array to an OCaml array

val string_of_eval : t -> string

string_of_eval e returns the string representation of evaluation e

type domain = E.domain
val of_domain : domain -> t

of_domain d converts d from type domain to type t.

Note: of_domain d doesn't create a copy of d

val to_domain : t -> domain

to_domain d converts d from type t to type domain.

Note: to_domain d doesn't create a copy of d

val zero : t

zero returns the evaluation representation of the zero polynomial

val is_zero : t -> bool

is_zero p checks whether a polynomial p is the zero polynomial

val degree : t -> int

degree returns the degree of a polynomial. Returns -1 for the zero polynomial

val length : t -> int

length e returns the size of domain where a polynomial is evaluated, or equally, the size of a C array where evaluation e is stored

val create : int -> t

create len returns the evaluation representation of a zero polynomial of size len

val copy : ?res:t -> t -> t

copy ?res a returns a copy of evaluation a. The function writes the result in res if res has the correct size and allocates a new array for the result otherwise

val get : t -> int -> scalar

get p i returns the i-th element of a given array p

val get_inplace : t -> int -> scalar -> unit

get_inplace p i res copies the i-th element of a given array p in res

val mul_by_scalar : scalar -> t -> t

mul_by_scalar computes muliplication of a polynomial by a blst_fr element

val mul_c : ?res:t -> evaluations:t list -> ?composition_gx:(int list * int) -> ?powers:int list -> unit -> t

mul_c computes p₁(gᶜ₁·x)ᵐ₁·p₂(gᶜ₂·x)ᵐ₂·…·pₖ(gᶜₖ·x)ᵐₖ, where

  • pᵢ = List.nth evaluations i
  • mᵢ = List.nth powers i
  • cᵢ = List.nth (fst composition_gx) i
  • n = snd composition_gx is the order of generator, i.e., gⁿ = 1

The function writes the result in res if res has the correct size (= min (size pᵢ)) and allocates a new array for the result otherwise

Note: res and pᵢ are disjoint

val linear_c : ?res:t -> evaluations:t list -> ?linear_coeffs:scalar list -> ?composition_gx:(int list * int) -> ?add_constant:scalar -> unit -> t

linear_c computes λ₁·p₁(gᶜ₁·x) + λ₂·p₂(gᶜ₂·x) + … + λₖ·pₖ(gᶜₖ·x) + add_constant, where

  • pᵢ = List.nth evaluations i
  • λᵢ = List.nth linear_coeffs i
  • cᵢ = List.nth (fst composition_gx) i
  • n = snd composition_gx is the order of generator, i.e., gⁿ = 1

The function writes the result in res if res has the correct size (= min (size pᵢ)) and allocates a new array for the result otherwise

Note: res and pᵢ are disjoint

val linear_with_powers : t list -> scalar -> t

linear_with_powers p s computes ∑ᵢ sⁱ·p.(i). This function is more efficient than linear + powers for evaluations of the same size

val add : ?res:t -> t -> t -> t

add ?res a b computes polynomial addition of a and b. The function writes the result in res if res has the correct size (= min (size (a, b))) and allocates a new array for the result otherwise

Note: res can be equal to either a or b

val equal : t -> t -> bool

equal a b checks whether a polynomial a is equal to a polynomial b

Note: equal is defined as restrictive equality, i.e., the same polynomial evaluated on different domains are said to be different

val evaluation_fft : domain -> polynomial -> t

evaluation_fft domain p converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build

Note:

  • size of domain must be a power of two
  • degree of polynomial must be strictly less than the size of domain
val interpolation_fft : domain -> t -> polynomial

interpolation_fft domain p converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build

Note:

  • size of domain must be a power of two
  • size of a polynomial must be equal to size of domain
val interpolation_fft2 : domain -> scalar array -> polynomial
val dft : domain -> polynomial -> t

dft domain polynomial converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build.

Computes the discrete Fourier transform in time O(n^2) where n = size domain.

requires:

  • size domain to divide Bls12_381.Fr.order - 1
  • size domain != 2^k
  • degree polynomial < size domain
val idft : domain -> t -> polynomial

idft domain t converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build.

Computes the inverse discrete Fourier transform in time O(n^2) where n = size domain.

requires:

  • size domain to divide Bls12_381.Fr.order - 1
  • size domain != 2^k
  • size domain = size t
val evaluation_fft_prime_factor_algorithm : domain1:domain -> domain2:domain -> polynomial -> t

evaluation_fft_prime_factor_algorithm domain1 domain2 p converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build. See the Prime-factor FFT algorithm.

requires:

  • size domain1 * size domain2 to divide Bls12_381.Fr.order - 1
  • size domain1 and size domain2 to be coprime
  • if for some k size domain1 != 2^k then size domain1 <= 2^10
  • if for some k size domain2 != 2^k then size domain2 <= 2^10
  • degree polynomial < size domain1 * size domain2
val interpolation_fft_prime_factor_algorithm : domain1:domain -> domain2:domain -> t -> polynomial

interpolation_fft_prime_factor_algorithm domain1 domain2 t converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build. See the Prime-factor FFT algorithm.

requires:

  • size domain1 * size domain2 to divide Bls12_381.Fr.order - 1
  • size domain1 and size domain2 to be coprime
  • if for some k size domain1 != 2^k then size domain1 <= 2^10
  • if for some k size domain2 != 2^k then size domain2 <= 2^10
  • size t = size domain1 * size domain2
val size_evaluations : t SMap.t -> int

size_evaluations returns the maximum size of elements in evaluations

val find_evaluation : t SMap.t -> string -> t

find_evaluation m name returns the evaluation for a given name name

val print_evaluations_name : t SMap.t -> unit

print_evaluations_name prints (name, degree, length) for each evaluation

val get_domain : t SMap.t -> domain

get_domain returns the evaluation for "X"

val compute_evaluations : domain:domain -> polynomial SMap.t -> t SMap.t

compute_evaluations converts the coefficient representation of each polynomial pᵢ to the evaluation representation.

Note:

  • size of domain must be a power of two
  • size of a polynomial pᵢ must be less than or equal to size of domain
val compute_evaluations_update_map : ?domain:domain -> evaluations:t SMap.t -> polynomial SMap.t -> t SMap.t

compute_evaluations_update_map writes the result of compute_evaluations in evaluations. If domain is not provided, get_domain is called

val mul : ?res:t -> evaluations:t SMap.t -> poly_names:string list -> ?composition_gx:(int list * int) -> ?powers:int list -> unit -> t

mul invokes mul_c with the evaluations for given names poly_names

val linear : ?res:t -> evaluations:t SMap.t -> poly_names:SMap.key list -> ?linear_coeffs:scalar list -> ?composition_gx:(int list * int) -> ?add_constant:scalar -> unit -> t

linear invokes linear_c with the evaluations for given names poly_names

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