Polynomial arithmetic demonstration using sparse representation.
This example demonstrates efficient polynomial arithmetic using a sparse representation with doubly linked lists (DynDlist). Polynomials are stored as sorted lists of non-zero terms, making operations efficient for polynomials with many zero coefficients. This is essential for symbolic computation and numerical analysis.
What is a Polynomial?
Mathematical Definition
A polynomial is an expression of the form:
P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ
Where:
- Coefficients: a₀, a₁, ..., aₙ are numbers
- Exponents: Powers of x (0, 1, 2, ..., n)
- Degree: Highest exponent n
Sparse vs Dense Representation
Dense Representation
- Storage: Store coefficients for ALL powers (even zeros)
- Array:
coeff[i] = coefficient of x^i
- Space: O(max_degree)
- Best for: Dense polynomials (few zeros)
- Example:
[5, 3, 0, 7, 0, 0, 2] represents 5 + 3x + 7x³ + 2x⁶
Sparse Representation (This Example)
- Storage: Store only non-zero terms
- List: List of (coefficient, exponent) pairs
- Space: O(number_of_nonzero_terms)
- Best for: Sparse polynomials (many zeros)
- Example:
[(5,0), (3,1), (7,3), (2,6)] represents same polynomial
When to Use Sparse?
Use sparse when:
- Many zeros: Most coefficients are zero
- High degree: Degree >> number of non-zero terms
- Memory: Memory is a concern
- Efficiency: Want faster operations on sparse data
Polynomial Structure
Term Representation
Each polynomial term (Termino) contains:
- Coefficient: The numeric multiplier (e.g., 5 in 5x³)
- Exponent: The power of x (e.g., 3 in 5x³)
Storage Order
Terms are stored sorted by exponent (ascending) for efficient operations:
- Merging: Easy to merge sorted lists
- Search: Binary search possible
- Traversal: Natural order
Supported Operations
Addition (p1 + p2, p1 += p2)
Algorithm: Merge two sorted lists
add(p1, p2):
result = []
i = 0, j = 0
result.append(p1[i])
i++
else if p1[i].
exp > p2[j].
exp:
result.append(p2[j])
j++
else:
result.append(p1[i].coeff + p2[j].coeff, p1[i].
exp)
i++, j++
__gmp_expr< T, __gmp_unary_expr< __gmp_expr< T, U >, __gmp_exp_function > > exp(const __gmp_expr< T, U > &expr)
size_t size(Node *root) noexcept
Time: O(n + m) where n, m are term counts Space: O(n + m) for result
Multiplication (p1 * p2)
Algorithm: Distribute and combine
multiply(p1, p2):
result = []
new_term = (t1.coeff * t2.coeff, t1.
exp + t2.
exp)
result.append(new_term)
combine_like_terms(result)
void each(size_t start, size_t end, Op &op)
Execute an operation repeatedly over a range of indices.
Distribute: (a·x^i) × (b·x^j) = (a·b)·x^(i+j) Time: O(n × m) for multiplication, O(n×m log(n×m)) with sorting Space: O(n × m) worst case
Subtraction (p1 - p2)
Algorithm: Negate and add
subtract(p1, p2):
negated_p2 = negate(p2)
return add(p1, negated_p2)
Time: O(n + m) - same as addition
Example Polynomials
Polynomial p1
Pattern: Odd powers from 1 to 19 Terms: X^1 + X^3 + X^5 + ... + X^19 Count: 10 terms Sparsity: Very sparse (only odd powers)
Polynomial p2
Pattern: All powers from 0 to 39 Terms: X^0 + X^1 + X^2 + ... + X^39 Count: 40 terms Sparsity: Dense (all powers present)
Operations Demonstrated
- p1 += p2: In-place addition (combines both polynomials)
- Result: All powers from 0 to 39, with doubled coefficients for odd powers
- p1 * p2: Multiplication (creates new polynomial)
- Result: Product polynomial with many terms
Complexity Analysis
| Operation | Dense | Sparse (this) | Improvement |
| Storage | O(degree) | O(terms) | Huge for sparse |
| Addition | O(degree) | O(terms₁ + terms₂) | Better for sparse |
| Multiplication | O(degree²) | O(terms₁ × terms₂) | Better for sparse |
| Evaluation | O(degree) | O(terms) | Better for sparse |
Example: High-Degree Sparse Polynomial
Polynomial: x^1000 + x^5000 + x^10000
Dense: O(10000) storage
Sparse: O(3) storage
Sparse is 3333× more efficient!
Applications
Symbolic Computation
- Computer algebra systems: Mathematica, Maple, SymPy
- Polynomial manipulation: Factor, expand, simplify
- Equation solving: Find roots, solve systems
Numerical Analysis
- Polynomial interpolation: Fit curves to data points
- Approximation: Approximate functions with polynomials
- Taylor series: Represent functions as polynomials
Cryptography
- Polynomial-based encryption: Some encryption schemes use polynomials
- Error-correcting codes: Reed-Solomon codes use polynomials
- Cryptographic protocols: Polynomial commitments
Signal Processing
- Digital filters: FIR/IIR filters use polynomial operations
- Transforms: Polynomial-based transforms
- Convolution: Polynomial multiplication = convolution
Graphics
- Bézier curves: Represented as polynomials
- Splines: Piecewise polynomial curves
- Surface modeling: Polynomial surfaces
Scientific Computing
- Series expansions: Represent functions as series
- Taylor polynomials: Approximate functions
- Numerical methods: Many methods use polynomials
Memory Efficiency
Example Comparison
Polynomial: x^100 + 5x^50 + 3x^10
Dense representation:
Array[101]: [3, 0, 0, ..., 5, 0, ..., 1]
Memory: 101 integers
Sparse representation:
List: [(3, 10), (5, 50), (1, 100)]
Memory: 3 pairs = 6 integers
Sparse saves 94% memory!
Usage
# Run polynomial arithmetic demo
./polinom
# The program demonstrates:
# - Creating sparse polynomials
# - Addition operations
# - Multiplication operations
# - Memory efficiency
For sparse polynomials, this representation is much more efficient!
Key Data Structures
DynDlist<Termino>: Doubly-linked list storing polynomial termsTermino: Structure with coefficient and exponent- Terms maintained in sorted order (by exponent)
- See also
- tpl_dynDlist.H Doubly linked list (used for storage)
-
matrix_example.C Sparse matrices (related sparse representation)
- Author
- Leandro Rabindranath León
Definition in file polinom.C.
1.9.8