polynomials

package module
v0.0.0-...-ab94cb0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 25, 2023 License: Apache-2.0 Imports: 7 Imported by: 1

README

Logo

Polynomials for Go

A Go package that handles the most essential polynomial operations

Usage

Import by:

import "github.com/mihonen/polynomials"

Derivatives

A derivative can be obtained by:

derivative := poly.Derivative()

Root Solving

The package has three methods for solving roots of polynomials.

Method Complex Roots Average solve time1 Robustness
Durand-Kerner ✅ 6.623µs 🥉
Bisection + Newton ❌ 7.38µs 🥈
Eigenvalue ✅ 142.292µs 🥇

1 Tested with 5 runs using polynomial: $P(x) = 1.13x^4 - 5.0x^3 + 12.0x^2 -2.8x + 3.213$

The package uses Quadratic formula to solve roots for simple qudratic polynomials. The default method for higher order polynomials computes the companion matrix of the polynomial and finds the eigenvalues of the matrix using mat package.

The second available method is a combination of bisection method and Newton-method as described in this and this page. This method first utilizes Sturm's theorem to seek for intervals which hold exactly one real root. It then finds the roots numerically using Newton's-method.

The third available method is the Durand-Kerner method. This method should be able to solve all complex roots for polynomials upto around 100 degrees.

Used method can be changed by changing the field SolveMode of the polynomial. For example

poly.SolveMode = polynomials.DurandKerner
Getting Complex Roots
roots, err := poly.ComplexRoots()
Getting Real Roots
roots, err := poly.Roots()

Examples

Solving Complex Roots for $P(x) = 3x^3 + 2x^2 -x + 13$
    a :=  3.0
    b :=  2.0
    c := -1.0
    d :=  13.0

    poly := polynomials.CreatePolynomial(a, b, c, d)

    roots, err := poly.ComplexRoots()
    if err != nil {
        log.Printf(`ComplexRoots() errored: %v`, err)
        return
    }
    // Use roots
Solving Real Roots for $P(x) = x^4 + 2x^2 -10$
    a :=  1.0
    b :=  0.0
    c :=  2.0
    d :=  0.0
    e := -10.0

    poly := polynomials.CreatePolynomial(a, b, c, d, e)

    roots, err := poly.Roots()
    if err != nil {
        log.Printf(`Roots() errored: %v`, err)
        return
    }
    // Use roots

Precision

The package solves roots to the 9th decimal by default. This can be adjusted in config.go if needed.

Testing

To run all tests, run the following command in terminal

go test

TODO

  • Check that root returned by Newton's method lies in the given interval

  • Add functionalities for solving minimums and maximums

  • Implement more robust complex root finding algorithm, that finds the eigenvalues of the companion matrix

Credits

This project is partly based on polygo by Sean Xie. We acknowledge and appreciate their work in the initial stages of this project.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var DefaultSolvingMethod = Eigenvalue
View Source 
var DurandKernerMaxIter = 5000
View Source 
var EpsDurand = 1e-10
View Source 
var EpsNewton = 1e-10 // max error allowed
View Source 
var MaxNewtonIterations = 25
View Source 
var RoundingDecimalPlaces = 12

Functions

func Reverse 

func Reverse[T comparable](s []T)

func Round 

func Round(value float64) float64

func RoundC 

func RoundC(z complex128) complex128

Complex Round

Types

type Interval 

type Interval struct {
	A float64
	B float64
}

func (*Interval) Mid 

func (i *Interval) Mid() float64

type Polynomial 

type Polynomial struct {
	SolveMode SolvingMethod
	// contains filtered or unexported fields
}

func CreatePolynomial 

func CreatePolynomial(coefficients ...float64) *Polynomial

CreatePolynomial returns a new Polynomial

func CreatePower 

func CreatePower(power int) *Polynomial

Creates simple power polynomial, eg. x^3

func (*Polynomial) Add 

func (poly1 *Polynomial) Add(poly2 *Polynomial) *Polynomial

func (*Polynomial) At 

func (poly *Polynomial) At(x float64) float64

At returns the value of the polynomial evaluated at x.

func (*Polynomial) AtComplex 

func (poly *Polynomial) AtComplex(z complex128) complex128

AtComplex returns the value of the polynomial evaluated at z

func (*Polynomial) Bound 

func (poly *Polynomial) Bound() float64

func (*Polynomial) Coeffs 

func (poly *Polynomial) Coeffs() []float64

func (*Polynomial) CompanionMatrix 

func (poly *Polynomial) CompanionMatrix() (*mat.Dense, error)

func (*Polynomial) ComplexRoots 

func (poly *Polynomial) ComplexRoots() ([]complex128, error)

func (*Polynomial) ComplexRootsDurandKerner 

func (poly *Polynomial) ComplexRootsDurandKerner() ([]complex128, error)

func (*Polynomial) ComplexRootsEigenvalue 

func (poly *Polynomial) ComplexRootsEigenvalue() ([]complex128, error)

func (*Polynomial) Degree 

func (poly *Polynomial) Degree() int

func (*Polynomial) Derivative 

func (poly *Polynomial) Derivative() *Polynomial

func (*Polynomial) DurandKernerRoots 

func (poly *Polynomial) DurandKernerRoots() ([]complex128, error)

func (*Polynomial) EhrlichRadius 

func (poly *Polynomial) EhrlichRadius() float64

func (*Polynomial) EuclideanDiv 

func (poly1 *Polynomial) EuclideanDiv(poly2 *Polynomial) (*Polynomial, *Polynomial)

func (*Polynomial) IsMonic 

func (poly *Polynomial) IsMonic() bool

func (*Polynomial) IsZero 

func (poly *Polynomial) IsZero() bool

func (*Polynomial) LeadingCoeff 

func (poly *Polynomial) LeadingCoeff() float64

func (*Polynomial) MakeMonic 

func (poly *Polynomial) MakeMonic()

func (*Polynomial) Mult 

func (poly1 *Polynomial) Mult(poly2 *Polynomial) *Polynomial

func (*Polynomial) NewtonMethod 

func (poly *Polynomial) NewtonMethod(guess float64) (float64, error)

Newton's Method Implementation https://en.wikipedia.org/wiki/Newton%27s_method

func (*Polynomial) PositiveRoots 

func (poly *Polynomial) PositiveRoots() ([]float64, error)

func (*Polynomial) QuadraticRoots 

func (poly *Polynomial) QuadraticRoots() []complex128

func (*Polynomial) RealRoots 

func (poly *Polynomial) RealRoots() ([]float64, error)

func (*Polynomial) RootBounds 

func (poly *Polynomial) RootBounds() (float64, float64)

func (*Polynomial) RootsBisectionNewton 

func (poly *Polynomial) RootsBisectionNewton() ([]float64, error)

func (*Polynomial) RootsWithin 

func (poly *Polynomial) RootsWithin(lowerBound float64, upperBound float64) ([]float64, error)

func (*Polynomial) RoundCoeffs 

func (poly *Polynomial) RoundCoeffs()

func (*Polynomial) ScalarMult 

func (poly *Polynomial) ScalarMult(s float64) *Polynomial

func (*Polynomial) ShiftRight 

func (poly *Polynomial) ShiftRight(offset int) *Polynomial

func (*Polynomial) String 

func (poly *Polynomial) String() string

String returns a string representation of the polynomial

func (*Polynomial) Sub 

func (poly1 *Polynomial) Sub(poly2 *Polynomial) *Polynomial

Subdivision of polynomials, returns result as a new polynomial

type SolvingMethod 

type SolvingMethod int
const (
	DurandKerner SolvingMethod = iota
	BisectionNewton
	Eigenvalue
)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.