NAME
Sidef::Types::Number::Polynomial - Univariate polynomial arithmetic and operations
DESCRIPTION
This class implements univariate polynomials with arbitrary-precision coefficients. Polynomials are represented as mathematical expressions in a single variable (typically 'x') with operations for arithmetic, evaluation, differentiation, root finding, and algebraic manipulation.
The Polynomial class supports both dense and sparse representations, allowing efficient storage and computation for polynomials with many zero coefficients.
SYNOPSIS
var a = Polynomial(5) # monomial: x^5
var b = Polynomial([1,2,3,4]) # x^3 + 2*x^2 + 3*x + 4
var c = Polynomial(5 => 3, 2 => 10) # 3*x^5 + 10*x^2
# Polynomial arithmetic
var sum = a + b # polynomial addition
var prod = a * b # polynomial multiplication
var quot = a / b # polynomial division
# Evaluation
say b.eval(2) # evaluate at x=2: 26
# Algebraic operations
say b.derivative # 3*x^2 + 4*x + 3
say b.roots # find all roots
say b.gcd(c) # greatest common divisorINHERITS
Inherits methods from:
* Sidef::Types::Number::NumberMETHODS
!=
a != bReturns true if polynomial a is not equal to polynomial b, false otherwise. Two polynomials are equal if they have the same degree and all corresponding coefficients are equal.
Aliases: ne
%
a % bReturns the remainder of polynomial division a divided by b. This computes the polynomial r such that a = q*b + r where the degree of r is less than the degree of b.
Aliases: mod
*
a * bReturns the product of polynomials a and b. Performs polynomial multiplication, with the resulting degree being the sum of the input degrees.
Polynomial([1,2,3]) * Polynomial([4,5]) # 4*x^3 + 13*x^2 + 22*x + 15Aliases: mul
**
a ** bReturns polynomial a raised to the power b. The exponent b must be a non-negative integer. For large exponents, uses efficient exponentiation algorithms.
Polynomial([1,1]) ** 3 # (x+1)^3 = x^3 + 3*x^2 + 3*x + 1Aliases: pow
+
a + bReturns the sum of polynomials a and b. Adds corresponding coefficients and returns a new polynomial.
Polynomial([1,2]) + Polynomial([3,4]) # 4*x + 6Aliases: add
++
a++Increments the polynomial by adding 1 to its constant term. Returns the new polynomial with the constant coefficient increased by one.
var p = Polynomial([1,2,3])
p++ # x^2 + 2*x + 4Aliases: inc
-
a - bReturns the difference of polynomials a minus b. Subtracts corresponding coefficients and returns a new polynomial.
Polynomial([1,2,3]) - Polynomial([0,1]) # x^2 + x + 3Aliases: sub
--
a--Decrements the polynomial by subtracting 1 from its constant term. Returns the new polynomial with the constant coefficient decreased by one.
var p = Polynomial([1,2,3])
p-- # x^2 + 2*x + 2Aliases: dec
/
a / bReturns the quotient of polynomial division a divided by b. This computes the polynomial q such that a = q*b + r where the degree of the remainder r is less than the degree of b.
Polynomial([1,0,-1]) / Polynomial([1,-1]) # x + 1Aliases: ÷, div
//
a // bReturns the integer quotient of polynomial division with specified rounding mode. This is similar to division but with options for different rounding behaviors.
Aliases: idiv, idiv_ceil, idiv_floor, idiv_round, idiv_trunc
<
a < bCompares polynomials a and b lexicographically. Returns true if a is less than b. Comparison is first by degree, then by leading coefficients.
Aliases: lt
<=>
a <=> bPerforms a three-way comparison between polynomials a and b. Returns -1 if a is less than b, 0 if they are equal, and 1 if a is greater than b.
Aliases: cmp
==
a == bReturns true if polynomial a is equal to polynomial b, false otherwise. Equality means same degree and all coefficients match.
Aliases: eq
>
a > bCompares polynomials a and b lexicographically. Returns true if a is greater than b.
Aliases: gt
≤
a ≤ bReturns true if polynomial a is less than or equal to polynomial b.
Aliases: <=, le
≥
a ≥ bReturns true if polynomial a is greater than or equal to polynomial b.
Aliases: >=, ge
abs
x.absReturns the absolute value of the polynomial. For polynomials, this typically returns a polynomial with the absolute value of the leading coefficient, or the magnitude measure appropriate for the polynomial ring.
binomial
n.binomial(k)Computes the binomial polynomial or binomial coefficient involving the polynomial. This operation depends on the polynomial structure and may compute generalized binomial expansions.
ceil
x.ceilReturns a polynomial with each coefficient rounded up to the nearest integer.
Polynomial([1.5, 2.3]).ceil # 2*x + 3coeff
x.coeff(k)Returns the coefficient of the term with degree k. If the polynomial does not have a term of degree k, returns 0.
var p = Polynomial([3,2,1]) # x^2 + 2*x + 3
p.coeff(1) # returns 2coeffs
x.coeffsReturns an array of all coefficients of the polynomial, ordered from highest degree to lowest degree (or lowest to highest depending on representation).
Polynomial([1,2,3]).coeffs # [1, 2, 3]cont
x.contReturns the content of the polynomial, which is the greatest common divisor of all its coefficients. This is useful for factoring out common factors.
Polynomial([6,9,12]).cont # returns 3Aliases: content
deg
x.degReturns the degree of the polynomial, which is the highest power of the variable with a non-zero coefficient. Returns -1 or negative infinity for the zero polynomial.
Polynomial([1,2,3]).deg # returns 2Aliases: degree
derivative
x.derivativeReturns the derivative of the polynomial with respect to its variable. Uses the power rule: the derivative of a*x^n is n*a*x^(n-1).
var p = Polynomial([1,0,3,2]) # x^3 + 3*x + 2
p.derivative # 3*x^2 + 3divmod
x.divmod(y)Performs polynomial division and returns both the quotient and remainder as a pair (array). Equivalent to computing both x / y and x % y.
var (q, r) = x.divmod(y)dump
x.dumpReturns a string representation of the polynomial's internal structure, useful for debugging. Shows the raw coefficient data and structure.
eval
x.eval(value)Evaluates the polynomial at the given value. Substitutes value for the variable and computes the result using Horner's method for efficiency.
var p = Polynomial([1,2,3]) # x^2 + 2*x + 3
p.eval(5) # 5^2 + 2*5 + 3 = 38exponents
x.exponentsReturns an array of all exponents (degrees) that have non-zero coefficients in the polynomial. Useful for sparse polynomial representations.
Polynomial(5 => 3, 2 => 1).exponents # [5, 2]float
x.floatConverts the polynomial to a floating-point representation by converting all coefficients to floating-point numbers.
floor
x.floorReturns a polynomial with each coefficient rounded down to the nearest integer.
Polynomial([1.8, 2.3]).floor # x + 2gcd
x.gcd(y)Computes the greatest common divisor of polynomials x and y. The GCD is the highest-degree polynomial that divides both input polynomials.
var p = Polynomial([1,0,-1]) # x^2 - 1
var q = Polynomial([1,-1]) # x - 1
p.gcd(q) # x - 1gcdext
x.gcdext(y)Extended Euclidean algorithm for polynomials. Returns a triple (g, s, t) where g is the GCD of x and y, and s, t are polynomials satisfying g = s*x + t*y (Bézout's identity).
height
x.heightReturns the height of the polynomial, typically defined as the maximum absolute value of its coefficients.
Polynomial([3,-5,2]).height # returns 5inv
x.invReturns the multiplicative inverse of the polynomial. This is typically only meaningful for constant polynomials or in polynomial rings modulo another polynomial.
invmod
x.invmod(m)Computes the multiplicative inverse of polynomial x modulo polynomial m. Returns a polynomial y such that x * y ≡ 1 (mod m), if such an inverse exists.
is_inf
x.is_infReturns true if the polynomial represents positive infinity, false otherwise. This is typically used for special polynomial objects.
is_mone
x.is_moneReturns true if the polynomial is equal to -1 (the constant polynomial -1), false otherwise.
is_nan
x.is_nanReturns true if the polynomial represents a "not-a-number" value, false otherwise. This typically indicates an invalid or undefined polynomial operation.
is_ninf
x.is_ninfReturns true if the polynomial represents negative infinity, false otherwise.
is_one
x.is_oneReturns true if the polynomial is equal to 1 (the constant polynomial 1), false otherwise. The constant 1 is the multiplicative identity for polynomials.
Polynomial([1]).is_one # true
Polynomial([1,0]).is_one # falseis_real
x.is_realReturns true if all coefficients of the polynomial are real numbers, false if any coefficient is complex.
is_squarefree
x.is_squarefreeReturns true if the polynomial is square-free, meaning it has no repeated factors. Equivalently, the polynomial and its derivative are coprime.
Polynomial([1,0,-1]).is_squarefree # true (x^2-1 = (x-1)(x+1))
Polynomial([1,0,0]).is_squarefree # false (x^2 = x*x)is_zero
x.is_zeroReturns true if the polynomial is the zero polynomial (all coefficients are zero), false otherwise.
Polynomial([0,0,0]).is_zero # true
Polynomial([0,0,1]).is_zero # falselcm
x.lcm(y)Computes the least common multiple of polynomials x and y. The LCM is the lowest-degree polynomial that is divisible by both input polynomials.
lcm(p, q) = (p * q) / gcd(p, q)leading_coeff
x.leading_coeffReturns the leading coefficient of the polynomial, which is the coefficient of the term with the highest degree.
Polynomial([3,2,1]).leading_coeff # returns 3Aliases: leading_coefficient
leading_monomial
x.leading_monomialReturns the leading monomial of the polynomial, which is the term with the highest degree (with coefficient 1).
Polynomial([3,2,1]).leading_monomial # x^2leading_term
x.leading_termReturns the leading term of the polynomial, which is the term with the highest degree including its coefficient.
Polynomial([3,2,1]).leading_term # 3*x^2lift
x.liftLifts the polynomial from a quotient ring back to the polynomial ring. This operation depends on the algebraic context and may convert modular polynomials to standard polynomials.
neg
x.negReturns the negation of the polynomial. Equivalent to multiplying by -1.
Polynomial([1,2,3]).neg # -x^2 - 2*x - 3new
Polynomial.new(args)Constructor for creating new polynomial objects. Accepts various argument formats:
Polynomial(5) # monomial x^5
Polynomial([1,2,3]) # x^2 + 2*x + 3
Polynomial(5 => 3, 2 => 1) # 3*x^5 + x^2Aliases: call
newton_method
f.newton_method(x0, df)Applies Newton's method to find a root of polynomial f starting from initial guess x0, using derivative df. Iteratively refines the approximation using the formula: x_{n+1} = x_n - f(x_n)/f'(x_n)
var f = Polynomial([1,0,-2]) # x^2 - 2
var df = f.derivative
f.newton_method(1.5, df) # approximate sqrt(2)norm
x.normReturns the norm of the polynomial, which may be defined as the Euclidean norm of its coefficient vector or another appropriate norm for the polynomial space.
powmod
x.powmod(n, m)Computes x^n mod m efficiently using modular exponentiation. Returns the polynomial x raised to power n and reduced modulo polynomial m.
pretty
x.prettyReturns a human-readable string representation of the polynomial in standard mathematical notation.
Polynomial([1,2,3]).pretty # "x^2 + 2*x + 3"prim_part
x.prim_partReturns the primitive part of the polynomial, which is the polynomial divided by its content (GCD of coefficients). This gives the polynomial with coprime integer coefficients.
Polynomial([6,9,12]).prim_part # 2*x^2 + 3*x + 4Aliases: primpart, primitive_part
rat
x.ratConverts the polynomial to a rational representation, converting all coefficients to rational numbers (Sidef Fraction objects).
rat_approx
x.rat_approxConverts floating-point coefficients to approximate rational numbers. Useful for finding simple fractional representations of decimal coefficients.
re
x.reReturns the real part of the polynomial. If all coefficients are real, returns the polynomial itself. If coefficients are complex, returns a polynomial with only the real parts.
Aliases: real
roots
f.rootsComputes and returns all roots (zeros) of the polynomial. The roots are the values where f(x) = 0. Returns an array of root values, which may include complex numbers.
Polynomial([1,0,-1]).roots # [-1, 1]round
x.round(r)Rounds all coefficients of the polynomial to r decimal places (or to nearest integers if r is omitted).
Polynomial([1.456, 2.789]).round(1) # 1.5*x + 2.8sgn
x.sgnReturns the sign of the polynomial, typically determined by the sign of the leading coefficient: -1 for negative, 0 for zero, 1 for positive.
sqr
x.sqrReturns the square of the polynomial. Equivalent to x * x.
Polynomial([1,1]).sqr # (x+1)^2 = x^2 + 2*x + 1squarefree_part
x.squarefree_partReturns the square-free part of the polynomial, which is the polynomial divided by the product of all its repeated factors. The result has no repeated roots.
Polynomial([1,0,0]).squarefree_part # x (removes one factor of x)to_n
x.to_nConverts the polynomial to a numeric value. For constant polynomials, returns the constant. For non-constant polynomials, behavior depends on implementation.
to_poly
x.to_polyReturns the polynomial object itself or converts an object to a polynomial. This is mainly used for type conversion and normalization.
to_s
x.to_sConverts the polynomial to a string representation. Returns a readable string showing the polynomial in standard mathematical notation.
Polynomial([1,2,3]).to_s # "Polynomial([1, 2, 3])"Aliases: stringify
EXAMPLES
Basic Polynomial Operations
# Create polynomials
var p = Polynomial([1, -2, 1]) # x^2 - 2*x + 1 = (x-1)^2
var q = Polynomial([1, -1]) # x - 1
# Arithmetic
var sum = p + q # x^2 - x
var product = p * q # x^3 - 3*x^2 + 3*x - 1
var (quotient, remainder) = p.divmod(q)
# Evaluation
say p.eval(3) # 9 - 6 + 1 = 4
say p.eval(1) # 0 (1 is a root)Calculus Operations
var p = Polynomial([1, 0, -3, 2]) # x^3 - 3*x + 2
# Differentiation
var dp = p.derivative # 3*x^2 - 3
var ddp = dp.derivative # 6*x
# Root finding
say p.roots # find all zerosAlgebraic Operations
var p = Polynomial([1, 0, -1]) # x^2 - 1
var q = Polynomial([1, -1]) # x - 1
# GCD and LCM
var g = p.gcd(q) # x - 1
var l = p.lcm(q) # x^2 - 1
# Extended GCD
var (gcd, s, t) = p.gcdext(q) # s*p + t*q = gcd
# Content and primitive part
var r = Polynomial([6, 9, 12])
say r.cont # 3
say r.prim_part # 2*x^2 + 3*x + 4Properties and Tests
var p = Polynomial([1, 0, -1])
say p.deg # 2
say p.is_squarefree # true
say p.leading_coeff # 1
say p.height # 1SEE ALSO
Sidef::Types::Number::Number, Sidef::Types::Number::Complex
AUTHOR
Daniel Șuteu