package odin-algebra:polynomial
Source

⌘K
Ctrl+K
or
/

    Overview

    Implementation of polynomials field over some underling algebraic structures.

    Index

    Constants (0)

    This section is empty.

    Variables (0)

    This section is empty.

    Procedures (118)

    Types

    Polynomial ¶
    Source

    Polynomial :: struct($T: typeid, $ST: typeid) {
	… // See source for fields
}
     

    This structure represents a polynomial of any degree. This should not be constructed directly the make_from_coefficients function should be used instead. The coefficients are stored so that there index is the power of x. The highest power coefficient should never be zero.

    Inputs:
    $T: the type of the coefficients $ST: the type of the algebraic structure used to operate on the coefficients

    Example: 
    Polynomial(f32, Numeric(f32))
Polynomial(Polynomial(f32, Numeric(f32)), EuclideanRing(f32))
    Related Procedures With Parameters
    Related Procedures With Returns

    PolynomialGeneratorInfo ¶
    Source

    PolynomialGeneratorInfo :: struct($T: typeid, $ST: typeid) {
	… // See source for fields
}

    SubResultantPseudoRemainderIterator ¶
    Source

    SubResultantPseudoRemainderIterator :: struct($T: typeid, $ST: typeid) {
	… // See source for fields
}
     

    iterator data structure for generating the sub resultant sequence made with make_sub_resultant_pseudo_remainder_iterator

    Related Procedures With Parameters
    Related Procedures With Returns

    Constants

    This section is empty.

    Variables

    This section is empty.

    Procedures

    add_ident_polynomial ¶
    Source

    add_ident_polynomial :: proc($T: typeid, algebraic_structure: $ST) -> Polynomial($T=typeid, $ST) {…}
     

    returns the additive identity polynomial ie the 0 polynomial

    add_numeric ¶
    Source

    add_numeric :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    add_ring ¶
    Source

    add_ring :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    cancel ¶
    Source

    cancel :: proc(ans: ^Polynomial($T, $ST), p: Polynomial($T, $ST), q: Polynomial($T, $ST)) {…}
     

    sets ans equal to p canceled by q ie if p = a * q then cancel(p, q) == a this procedure panics if q does not divide p ie if p is not a multiple of q

    cancel_div_field ¶
    Source

    cancel_div_field :: proc(quot: ^Polynomial($T, $ST), rem: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST), allocator: runtime.Allocator) {…}

    cancel_div_numeric ¶
    Source

    cancel_div_numeric :: proc(quot: ^Polynomial($T, $ST), rem: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST), allocator: runtime.Allocator) {…}

    degree ¶
    Source

    degree :: proc(p: Polynomial($T, $ST)) -> untyped integer {…}
     

    returns the degree of a polynomial -1 is returned of the zero polynomial

    delete_generator ¶
    Source

    delete_generator :: proc(gen: prop_test.Generator($T=Polynomial($T, $ST))) {…}

    delete_polynomial ¶
    Source

    delete_polynomial :: proc(p: Polynomial($T, $ST)) {…}
     

    deletes a polynomial also deletes the coefficients using the underlying algebraic structure

    delete_polynomial_commutative_ring ¶
    Source

    delete_polynomial_commutative_ring :: proc(v: ring.CommutativeRing($T=Polynomial($T, $ST))) {…}

    delete_polynomial_euclidean_ring ¶
    Source

    delete_polynomial_euclidean_ring :: proc(v: euclidean_ring.EuclideanRing($T=Polynomial($T, $ST))) {…}

    delete_polynomial_integral_domain ¶
    Source

    delete_polynomial_integral_domain :: proc(v: integral_domain.IntegralDomain($T=Polynomial($T, $ST))) {…}

    delete_polynomial_ring ¶
    Source

    delete_polynomial_ring :: proc(v: ring.Ring($T=Polynomial($T, $ST))) {…}

    delete_sub_resultant_pseudo_remainder_iterator ¶
    Source

    delete_sub_resultant_pseudo_remainder_iterator :: proc(it: SubResultantPseudoRemainderIterator($T, $ST)) {…}

    differentiate_numeric ¶
    Source

    differentiate_numeric :: proc(p: Polynomial($T, $ST)) -> Polynomial($T, $ST) {…}

    differentiate_ring ¶
    Source

    differentiate_ring :: proc(p: Polynomial($T, $ST)) -> Polynomial($T, $ST) {…}

    div_field ¶
    Source

    div_field :: proc(quot: ^Polynomial($T, $ST), rem: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    div_numeric ¶
    Source

    div_numeric :: proc(quot: ^Polynomial($T, $ST), rem: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    eq_base ¶
    Source

    eq_base :: proc(p: Polynomial($T, $ST), q: Polynomial($T, $ST)) -> bool {…}

    eq_numeric ¶
    Source

    eq_numeric :: proc(p: Polynomial($T, $ST), q: Polynomial($T, $ST)) -> bool {…}

    eval_same_type ¶
    Source

    eval_same_type :: proc(p: Polynomial($T, $ST), x: $T) -> $T {…}

    eval_to_coefficient_type ¶
    Source

    eval_to_coefficient_type :: proc(p: Polynomial($T, $ST), x: $V, s_mul: proc(ans: ^$T, t: $T, s: $V)) -> $T {…}
     

    use this when you expect the output type to be the coefficient type s_mul should set ans = t * s

    eval_to_x_type ¶
    Source

    eval_to_x_type :: proc(p: Polynomial($T, $ST), x: $V, ring_x: $SV, s_add: proc(ans: ^$V, t: $T, s: $V)) -> $V {…}
     

    use this when you expect the output type to be the type of x s_add should set ans = t + s

    integrate_field ¶
    Source

    integrate_field :: proc(p: Polynomial($T, $ST), c: $T) -> Polynomial($T, $ST) {…}

    integrate_numeric ¶
    Source

    integrate_numeric :: proc(p: Polynomial($T, $ST), c: $T) {…}

    is_valid ¶
    Source

    is_valid :: proc(p: Polynomial($T, $ST)) -> bool {…}
     

    determines if a polynomial is valid a polynomial is valid if it is the zero polynomial or its leading coefficient is not zero

    log_polynomial ¶
    Source

    log_polynomial :: proc(p: Polynomial($T, $ST)) {…}
     

    logs a polynomial to context.logger in the standard way

    make_from_coefficients_algebraic_structure ¶
    Source

    make_from_coefficients_algebraic_structure :: proc($T: typeid, algebraic_structure: $ST, coefficients: []typeid, allocator := context.allocator) -> Polynomial($T=typeid, $ST) {…}

    make_from_coefficients_numeric ¶
    Source

    make_from_coefficients_numeric :: proc($T: typeid, coefficients: []typeid, allocator := context.allocator) -> Polynomial($T=typeid, $ST=NumericField($T=typeid)) {…}

    make_generator ¶
    Source

    make_generator :: proc(coefficient_generator: prop_test.Generator($T), coefficient_algebraic_structure: $ST) -> prop_test.Generator($T=Polynomial($T, $ST)) {…}
     

    makes a generator for polynomials given a generator of there coefficients used for property based testing of polynomials

    make_polynomial_base ¶
    Source

    make_polynomial_base :: proc($T: typeid, coefficients_structure: $ST) -> base.Base($T=Polynomial($T=typeid, $ST)) {…}
     

    makes an base structure for a polynomial given the coefficients base structure

    make_polynomial_commutative_ring ¶
    Source

    make_polynomial_commutative_ring :: proc($T: typeid, coeffiencet_structure: $ST) -> ring.CommutativeRing($T=Polynomial($T=typeid, $ST)) {…}
     

    makes an commutative ring structure for a polynomial given the coefficients commutative ring structure

    make_polynomial_euclidean_ring ¶
    Source

    make_polynomial_euclidean_ring :: proc($T: typeid, coefficient_structure: $ST) -> euclidean_ring.EuclideanRing($T=Polynomial($T=typeid, $ST)) {…}
     

    makes an euclidean ring structure for a polynomial given the coefficients field structure note: to perform euclidean divison on a polynomial a multiplicative inverse must exist for the coefficients since divison must be performed on the coefficients

    make_polynomial_integral_domain ¶
    Source

    make_polynomial_integral_domain :: proc($T: typeid, coefficient_structure: $ST) -> integral_domain.IntegralDomain($T=Polynomial($T=typeid, $ST)) {…}
     

    makes an integral domain structure for a polynomial given the coefficients integral domain structure

    make_polynomial_ring ¶
    Source

    make_polynomial_ring :: proc($T: typeid, coeffiencet_structure: $ST) -> ring.Ring($T=Polynomial($T=typeid, $ST)) {…}
     

    makes an ring structure for a polynomial given the coefficients ring structure

    make_sub_resultant_pseudo_remainder_iterator ¶
    Source

    make_sub_resultant_pseudo_remainder_iterator :: proc(p: Polynomial($T, $ST), q: Polynomial($T, $ST)) -> SubResultantPseudoRemainderIterator($T, $ST) {…}
     

    makes a sub resultant sequence itterator that can be itterated through with next_sub_resultant to obtain the sub resultant chain

    make_uninitialized_algebraic_structure ¶
    Source

    make_uninitialized_algebraic_structure :: proc($T: typeid, algebraic_structure: $ST, degree: untyped integer, loc := #caller_location) -> Polynomial($T=typeid, $ST) {…}

    make_uninitialized_numeric ¶
    Source

    make_uninitialized_numeric :: proc($T: typeid, degree: untyped integer, loc := #caller_location) -> Polynomial($T=typeid, $ST=NumericField($T=typeid)) {…}

    mul_ident_polynomial ¶
    Source

    mul_ident_polynomial :: proc($T: typeid, algebraic_structure: $ST) -> Polynomial($T=typeid, $ST) {…}
     

    returns the multiplicative identity polynomial ie the 1 polynomial

    mul_independent_numeric ¶
    Source

    mul_independent_numeric :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}
     

    polynomial multiplication where ans, l and r are indepeneted ie they there coefficients are all in differnt memory

    mul_independent_ring ¶
    Source

    mul_independent_ring :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}
     

    polynomial multiplication where ans, l and r are indepeneted ie they there coefficients are all in differnt memory

    mul_numeric ¶
    Source

    mul_numeric :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    mul_ring ¶
    Source

    mul_ring :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    mul_self_by_other_numeric ¶
    Source

    mul_self_by_other_numeric :: proc(ans: ^Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}
     

    polynomial sets ans = ans * r

    mul_self_by_other_ring_left ¶
    Source

    mul_self_by_other_ring_left :: proc(ans: ^Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}
     

    polynomial = opertation sets ans = ans r

    mul_self_by_other_ring_right ¶
    Source

    mul_self_by_other_ring_right :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST)) {…}
     

    polynomial sets ans = l * ans

    mul_self_numeric ¶
    Source

    mul_self_numeric :: proc(ans: ^Polynomial($T, $ST)) {…}
     

    polynomial self multiplication sets ans to ans * ans

    mul_self_ring ¶
    Source

    mul_self_ring :: proc(ans: ^Polynomial($T, $ST)) {…}
     

    polynomial self multiplication sets ans to ans * ans

    muli_var_eval ¶
    Source

    muli_var_eval :: proc(p: Polynomial($T, $ST), x: [0]$C, ring_x: $SC, s_add: proc(ans: ^$C, t: $U, s: $C)) -> $C {…}
     

    s_add should set ans = t + s

    neg ¶
    Source

    neg :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST)) {…}
     

    polynomial negation sets ans = -l

    next_sub_resultant ¶
    Source

    next_sub_resultant :: proc(it: ^SubResultantPseudoRemainderIterator($T, $ST)) -> Polynomial($T, $ST) {…}
     

    given an iterator returns the next sub resultant in the chain moving the iterator forwards when there are no more sub resultants in the chain this returns 0

    prepend_fixed_length ¶
    Source

    prepend_fixed_length :: proc($N := , t: $T, ts: [0]$T) -> [0]$T {…}
    print_polynomial :: proc(p: Polynomial($T, $ST)) {…}
     

    prints a polynomial using fmt

    real_roots ¶
    Source

    real_roots :: proc(p: Polynomial($T, $ST)) -> []$T {…}
     

    uses the durand–kerner method to return the complex roots then filters the roots to only roots with small imaginary components

    resize_or_init_polynomial ¶
    Source

    resize_or_init_polynomial :: proc(p: ^Polynomial($T, $ST), algebraic_structure: $ST, new_degree: untyped integer, loc := #caller_location) {…}

    resultant ¶
    Source

    resultant :: proc(p: Polynomial($T, $ST), q: Polynomial($T, $ST)) -> $T {…}
     

    computes the resultant of 2 polynomials

    roots_complex128 ¶
    Source

    roots_complex128 :: proc(p: Polynomial($T, $ST)) -> []complex128 {…}

    roots_complex32 ¶
    Source

    roots_complex32 :: proc(p: Polynomial($T, $ST)) -> []complex32 {…}

    roots_complex64 ¶
    Source

    roots_complex64 :: proc(p: Polynomial($T, $ST)) -> []complex64 {…}

    roots_match ¶
    Source

    roots_match :: proc(r1: [0]$C, r2: [0]$C) -> bool {…}

    roots_numeric ¶
    Source

    roots_numeric :: proc($C: typeid, p: Polynomial($T, $ST), max_iterations: untyped integer = 100) -> []typeid {…}

    s_cancel ¶
    Source

    s_cancel :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), s: $T) {…}
     

    cancels each coefficient in l by s and writes the answer to ans

    s_mul ¶
    Source

    s_mul :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), s: $T) {…}
     

    multiplies each coefficient in l by s and writes the answer to ans

    sb_print_polynomial_base ¶
    Source

    sb_print_polynomial_base :: proc(builder: ^strings.Builder, p: Polynomial($T, $ST)) {…}

    sb_print_polynomial_numeric ¶
    Source

    sb_print_polynomial_numeric :: proc(builder: ^strings.Builder, p: Polynomial($T, $ST)) {…}

    set_base ¶
    Source

    set_base :: proc(l: ^Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    set_numeric ¶
    Source

    set_numeric :: proc(l: ^Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    shrink_to_valid ¶
    Source

    shrink_to_valid :: proc(p: ^Polynomial($T, $ST)) {…}
     

    shrinks a polynomial that may or may not be valid to a valid polynomial by removing leading zeros

    solve_system ¶
    Source

    solve_system :: proc($N_VARS := , $C: typeid, polynomials: [0]Polynomial($T, $ST)) -> [][0]typeid {…}
     

    solves a multi variable system of equations expects the number of equations to match the number of variables

    sub_numeric ¶
    Source

    sub_numeric :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    sub_ring ¶
    Source

    sub_ring :: proc(ans: ^Polynomial($T, $ST), l: Polynomial($T, $ST), r: Polynomial($T, $ST)) {…}

    test_add_1 ¶
    Source

    test_add_1 :: proc(t: ^testing.T) {…}

    test_add_2 ¶
    Source

    test_add_2 :: proc(t: ^testing.T) {…}

    test_add_3 ¶
    Source

    test_add_3 :: proc(t: ^testing.T) {…}

    test_add_4 ¶
    Source

    test_add_4 :: proc(t: ^testing.T) {…}

    test_calc_prop_based ¶
    Source

    test_calc_prop_based :: proc(t: ^testing.T) {…}

    test_cancel_1 ¶
    Source

    test_cancel_1 :: proc(t: ^testing.T) {…}

    test_differentiate_1 ¶
    Source

    test_differentiate_1 :: proc(t: ^testing.T) {…}

    test_differentiate_2 ¶
    Source

    test_differentiate_2 :: proc(t: ^testing.T) {…}

    test_div_1 ¶
    Source

    test_div_1 :: proc(t: ^testing.T) {…}

    test_div_2 ¶
    Source

    test_div_2 :: proc(t: ^testing.T) {…}

    test_div_3 ¶
    Source

    test_div_3 :: proc(t: ^testing.T) {…}

    test_div_4 ¶
    Source

    test_div_4 :: proc(t: ^testing.T) {…}

    test_div_5 ¶
    Source

    test_div_5 :: proc(t: ^testing.T) {…}

    test_div_6 ¶
    Source

    test_div_6 :: proc(t: ^testing.T) {…}

    test_div_7 ¶
    Source

    test_div_7 :: proc(t: ^testing.T) {…}

    test_div_8 ¶
    Source

    test_div_8 :: proc(t: ^testing.T) {…}

    test_eq_1 ¶
    Source

    test_eq_1 :: proc(t: ^testing.T) {…}

    test_eq_2 ¶
    Source

    test_eq_2 :: proc(t: ^testing.T) {…}

    test_eq_3 ¶
    Source

    test_eq_3 :: proc(t: ^testing.T) {…}

    test_eq_4 ¶
    Source

    test_eq_4 :: proc(t: ^testing.T) {…}

    test_eval_1 ¶
    Source

    test_eval_1 :: proc(t: ^testing.T) {…}

    test_eval_2 ¶
    Source

    test_eval_2 :: proc(t: ^testing.T) {…}

    test_mul_1 ¶
    Source

    test_mul_1 :: proc(t: ^testing.T) {…}

    test_mul_2 ¶
    Source

    test_mul_2 :: proc(t: ^testing.T) {…}

    test_mul_3 ¶
    Source

    test_mul_3 :: proc(t: ^testing.T) {…}

    test_mul_4 ¶
    Source

    test_mul_4 :: proc(t: ^testing.T) {…}

    test_mul_5 ¶
    Source

    test_mul_5 :: proc(t: ^testing.T) {…}

    test_mul_6 ¶
    Source

    test_mul_6 :: proc(t: ^testing.T) {…}

    test_polynomial_over_i64_integral_domain_axioms ¶
    Source

    test_polynomial_over_i64_integral_domain_axioms :: proc(t: ^testing.T) {…}

    test_polynomial_over_i64_integral_domain_safety_axioms ¶
    Source

    test_polynomial_over_i64_integral_domain_safety_axioms :: proc(t: ^testing.T) {…}

    test_polynomial_over_polynomial_over_i64_integral_domain_axioms ¶
    Source

    test_polynomial_over_polynomial_over_i64_integral_domain_axioms :: proc(t: ^testing.T) {…}

    test_polynomial_over_polynomial_over_i64_integral_safety_axioms ¶
    Source

    test_polynomial_over_polynomial_over_i64_integral_safety_axioms :: proc(t: ^testing.T) {…}

    test_polynomial_pow ¶
    Source

    test_polynomial_pow :: proc(t: ^testing.T) {…}

    test_real_roots ¶
    Source

    test_real_roots :: proc(t: ^testing.T) {…}

    test_ref_add_3 ¶
    Source

    test_ref_add_3 :: proc(t: ^testing.T) {…}

    test_ref_sub_2 ¶
    Source

    test_ref_sub_2 :: proc(t: ^testing.T) {…}

    test_ref_sub_3 ¶
    Source

    test_ref_sub_3 :: proc(t: ^testing.T) {…}

    test_resultant_1 ¶
    Source

    test_resultant_1 :: proc(t: ^testing.T) {…}

    test_resultant_2 ¶
    Source

    test_resultant_2 :: proc(t: ^testing.T) {…}

    test_resultant_3 ¶
    Source

    test_resultant_3 :: proc(t: ^testing.T) {…}

    test_resultant_4 ¶
    Source

    test_resultant_4 :: proc(t: ^testing.T) {…}

    test_roots ¶
    Source

    test_roots :: proc(t: ^testing.T) {…}

    test_solve_system ¶
    Source

    test_solve_system :: proc(t: ^testing.T) {…}

    test_sub_1 ¶
    Source

    test_sub_1 :: proc(t: ^testing.T) {…}

    test_sub_2 ¶
    Source

    test_sub_2 :: proc(t: ^testing.T) {…}

    test_sub_3 ¶
    Source

    test_sub_3 :: proc(t: ^testing.T) {…}

    test_sub_resultant_pseudo_remainder_seq ¶
    Source

    test_sub_resultant_pseudo_remainder_seq :: proc(t: ^testing.T) {…}

    Procedure Groups

    add ¶
    Source

    add :: proc{
	add_ring,
	add_numeric,
}
     

    polynomial addition sets ans to l + r

    cancel_div ¶
    Source

    cancel_div :: proc{
	cancel_div_field,
	cancel_div_numeric,
}
     

    a special kind of divison for when it can be assumed that all division operations on the coefiencet integral domain are perfect

    differentiate ¶
    Source

    differentiate :: proc{
	differentiate_numeric,
	differentiate_ring,
}

    div ¶
    Source

    div :: proc{
	div_field,
	div_numeric,
}
     

    performs euclidean divison on a polynomial such that l = quot * r + rem

    eq ¶
    Source

    eq :: proc{
	eq_base,
	eq_numeric,
}
     

    checks if 2 polynomials are equal

    eval ¶
    Source

     

    evaluates the polynomial at x

    integrate ¶
    Source

    integrate :: proc{
	integrate_field,
	integrate_numeric,
}
     

    polynomial must be over a field since we need to be able to divide to integrate

    make_from_coefficients ¶
    Source

     

    Makes a polynomial from the coefficients. Clones the slice so the slice can go off the stack. Does not clone the underlying data structures.

    make_uninitialized ¶
    Source

     

    used to make uninitialized polynomials unless you set degree to -1 the returned polynomial will not be valid since all its coefficients will be 0

    mul ¶
    Source

    mul :: proc{
	mul_ring,
	mul_numeric,
}
     

    polynomial multiplication sets ans = l * r

    roots ¶
    Source

     

    uses the durand–kerner method to return the complex roots

    sb_print_polynomial ¶
    Source

    sb_print_polynomial :: proc{
	sb_print_polynomial_base,
	sb_print_polynomial_numeric,
}
     

    prints a polynomial to the input string builder

    set ¶
    Source

    set :: proc{
	set_base,
	set_numeric,
}
     

    sets l equal to a clone of r

    sub ¶
    Source

    sub :: proc{
	sub_ring,
	sub_numeric,
}
     

    polynomial subtraction sets ans to l - r

    Source Files

    Generation Information

    Generated with odin version dev-2025-04 (vendor "odin") Linux_amd64 @ 2025-05-13 09:15:55.505399271 +0000 UTC