find-real-roots-of-polynomial

Crates.iofind-real-roots-of-polynomial
lib.rsfind-real-roots-of-polynomial
version0.2.3
sourcesrc
created_at2021-07-10 16:57:47.796164
updated_at2024-03-17 07:46:16.174906
descriptionfind all real roots of a polynomial
homepage
repositoryhttps://gitlab.com/Toru3/find-real-roots-of-polynomial
max_upload_size
id421145
size19,149
(Toru3)

documentation

https://docs.rs/find-real-roots-of-polynomial

README

calculate Sturm chain and find all real roots by Sturm method.

use find_real_roots_of_polynomial::SturmChain;
use polynomial_ring::{polynomial, Polynomial};
use num::{BigRational, BigInt};
let v = [-2, 0, 1].iter().map(|x| BigRational::from(BigInt::from(*x))).collect::<Vec<_>>();
let f = Polynomial::new(v); // f=x^2-2=(x-√2)(x+√2)
let limit = BigRational::new(BigInt::from(1), BigInt::from(16)); // 1/16
let sc = SturmChain::<BigRational>::new(f);
let roots = sc.find_all_real_roots(&limit);
assert_eq!(roots.len(), 2);
assert!(&roots[0].1 - &roots[0].0 < limit);
assert!(&roots[1].1 - &roots[1].0 < limit);
// -√2 ∈ [-93/64, -45/32] = [-1.453125, -1.40625]
//  √2 ∈ [45/32, 93/64] = [1.40625, 1.453125]
assert_eq!(roots[0].0, BigRational::new(BigInt::from(-93), BigInt::from(64)));
assert_eq!(roots[0].1, BigRational::new(BigInt::from(-45), BigInt::from(32)));
assert_eq!(roots[1].0, BigRational::new(BigInt::from(45), BigInt::from(32)));
assert_eq!(roots[1].1, BigRational::new(BigInt::from(93), BigInt::from(64)));

Licence

AGPL-3.0-or-later

Commit count: 8

cargo fmt