gifnksm/polynomial-rs

Manipulations and data types that represent polynomial

polynomial-rs's Issues

Avoid cloning where possible

Most methods and trait impls use a lot of cloning. This is not desirable when using BigInt or BigRational for coefficients, so it would be nice to avoid cloning where possible.

Is this project abandoned?

@gifnksm this project looks pretty abandoned (last activity was 2018), are you still interested in maintaining it?

Ideas for const polynomials?

Right now polynomial requires a Vec. It would be useful to have either a smallvec or a fixed array to avoid heap allocations.

This would let me write a library that exports polynomials as constants. IE the first complete elliptic integral for use in high-performance simulations.

Any of [T; N] or &'static T would be useful.

Incorrect polynomial fitment

The degree 2 polynomial to $f(0)=3849; f(1)=34331; f(2)=95175$ is incorrectly fitted.

This library returns: $3848 + 15303 x + 15180 x^2 $
The correct result is: $3849 + 15301 x + 15181 x^2 $
Error: $-1 + 2x -1x^2$
This can be verified by res-subsituting the variables. In particular, the error in $f(0)$ is trivial

Wolframalpha gives the correct result

Reproduction

Cargo.toml

[dependencies]
polynomial = "0.2.6"

src/main.rs

use polynomial::Polynomial;
fn main() {
    let xs = vec![0, 1, 2];
    let ys = vec![3849, 34331, 95175];

    let poly = Polynomial::lagrange(&xs, &ys).unwrap();
    println!("{}", poly.pretty("x")); //3848+15303*x+15180*x^2
}

This was found during AOC Day21, and was responsible for quite some hours of debugging :^|

Polynomial division

Add support for polynomial division and remainder.

Evaluation using Horner's method

Currently the implementation of Polynomial::eval seems not optimal. We can always apply the property of Distributivity of multiplication over addition to reduce the computational complexity.