polyn

Documentation

Overview

Package polyn is for arithmetic with linear polynomials and linear equations.

BSD 3-Clause License

Copyright (c) 2017–21, Norbert Pillmayer.

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

• func ArityComparator(polyn1, polyn2 interface{}) int
• func T() tracing.Trace
• func TraceStringVar(i int, resolv VariableResolver) string
• type LinEqSolver
  • func CreateLinEqSolver() *LinEqSolver
  • func (leq *LinEqSolver) AddEq(p Polynomial) *LinEqSolver
  • func (leq *LinEqSolver) AddEqs(plist []Polynomial) *LinEqSolver
  • func (leq *LinEqSolver) Dump(resolv VariableResolver)
  • func (leq *LinEqSolver) PolynString(p Polynomial) string
  • func (leq *LinEqSolver) SetVariableResolver(resolver VariableResolver)
  • func (leq *LinEqSolver) VarString(i int) string
• type Polynomial
  • func New(c float64, tms ...X) (Polynomial, error)
  • func NewConstantPolynomial(c float64) Polynomial
  • func (p Polynomial) Add(p2 Polynomial, destructive bool) Polynomial
  • func (p Polynomial) CopyPolynomial() Polynomial
  • func (p Polynomial) Divide(p2 Polynomial, destructive bool) Polynomial
  • func (p Polynomial) GetCoeffForTerm(i int) float64
  • func (p Polynomial) GetConstantValue() float64
  • func (p Polynomial) IsConstant() (float64, bool)
  • func (p Polynomial) IsValid() bool
  • func (p Polynomial) IsVariable() (int, bool)
  • func (p Polynomial) Multiply(p2 Polynomial, destructive bool) Polynomial
  • func (p Polynomial) SetTerm(i int, scale float64) Polynomial
  • func (p Polynomial) String() string
  • func (p Polynomial) Subtract(p2 Polynomial, destructive bool) Polynomial
  • func (p Polynomial) TraceString(resolv VariableResolver) string
  • func (p Polynomial) Zap() Polynomial
• type VariableResolver
• type X

Functions

func ArityComparator

func ArityComparator(polyn1, polyn2 interface{}) int

ArityComparator is a Comparator for polynomials. Polynomials are "smaller" if their arity is smaller, i.e. they have less unknown variables.

func T

func T() tracing.Trace

T traces to the equations tracer.

func TraceStringVar

func TraceStringVar(i int, resolv VariableResolver) string

TraceStringVar is a helper for tracing output. Parameter resolv may be nil.

Types

type LinEqSolver

type LinEqSolver struct {
	// contains filtered or unexported fields
}

LinEqSolver is a container for linear equations. Used to incrementally solve systems of linear equations.

Inspired by Donald E. Knuth's MetaFont, John Hobby's MetaPost and by a Lua project by John D. Ramsdell: http://luaforge.net/projects/lineqpp/

func CreateLinEqSolver

func CreateLinEqSolver() *LinEqSolver

CreateLinEqSolver creates a new sytem of linear equations.

func (*LinEqSolver) AddEq

func (leq *LinEqSolver) AddEq(p Polynomial) *LinEqSolver

AddEq adds a new equation 0 = p (p is Polynomial) to a system of linear equations. Immediately starts to solve the -- possibly incomplete -- system, as far as possible.

func (*LinEqSolver) AddEqs

func (leq *LinEqSolver) AddEqs(plist []Polynomial) *LinEqSolver

AddEqs adds a set of linear equations to the LEQ system. See AddEq.

func (*LinEqSolver) Dump

func (leq *LinEqSolver) Dump(resolv VariableResolver)

Dump is a debugging helper to dump all known equations.

func (*LinEqSolver) PolynString

func (leq *LinEqSolver) PolynString(p Polynomial) string

PolynString outputs a polynomial as string. Uses VariableResolver, if present.

func (*LinEqSolver) SetVariableResolver

func (leq *LinEqSolver) SetVariableResolver(resolver VariableResolver)

SetVariableResolver sets a variable resolver. Within the LEQ variables are encoded by their serial ID, which is used as their position within polynomias. Example: variable "n[3].a" with ID=4711 will become x.4711 internally. The resolver maps "x.4711" to "n[3].a".

func (*LinEqSolver) VarString

func (leq *LinEqSolver) VarString(i int) string

VarString returns a readable variable name for an internal variable. Uses a VariableResolver, if present.

type Polynomial

type Polynomial struct {
	Terms *treemap.Map
}

Polynomial is a type for linear polynomials

c + a.1 x.1 + a.2 x.2 + ... a.n x.n .

We store the coefficients only. Index 0 is the constant term. We store the scales/coeff in a TreeMap (sorted map). Coefficients are of type float64.

func New

func New(c float64, tms ...X) (Polynomial, error)

New creates a polygon, given the term coefficients and exponents

Use it as

polyn.New(8, polyn.X{2,5}, polyn.X{1,2/3} )

to get

P(x) = 8 + 5a + 2/3b

func NewConstantPolynomial

func NewConstantPolynomial(c float64) Polynomial

NewConstantPolynomial creates a Polynomial consisting of just a constant term.

func (Polynomial) Add

func (p Polynomial) Add(p2 Polynomial, destructive bool) Polynomial

Add adds two Polynomials. Returns a new Polynomial, except when the 'destructive'-flag is set (then p is altered).

func (Polynomial) CopyPolynomial

func (p Polynomial) CopyPolynomial() Polynomial

CopyPolynomial makes a copy of a numeric Polynomial.

func (Polynomial) Divide

func (p Polynomial) Divide(p2 Polynomial, destructive bool) Polynomial

Divide divides two polynomial by a numeric (not 0). p2 will be destroyed.

func (Polynomial) GetCoeffForTerm

func (p Polynomial) GetCoeffForTerm(i int) float64

GetCoeffForTerm gets the coefficient for term # i.

Example:

p = x + 3x.2

⇒

coeff(2) = 3

func (Polynomial) GetConstantValue

func (p Polynomial) GetConstantValue() float64

GetConstantValue returns the constant term of a polynomial.

func (Polynomial) IsConstant

func (p Polynomial) IsConstant() (float64, bool)

IsConstant checks wether a Polynomial is a constant, i.e. p = { c }? Returns the constant and a flag.

func (Polynomial) IsValid

func (p Polynomial) IsValid() bool

IsValid checks if this a correctly initialized polynomial.

func (Polynomial) IsVariable

func (p Polynomial) IsVariable() (int, bool)

IsVariable checks wether a Polynomial is a variable?, i.e. a single term with coefficient = 1. Returns the position of the term and a flag.

func (Polynomial) Multiply

func (p Polynomial) Multiply(p2 Polynomial, destructive bool) Polynomial

Multiply multiplys two Polynomials. One of both must be a constant. p2 will be destroyed.

func (Polynomial) SetTerm

func (p Polynomial) SetTerm(i int, scale float64) Polynomial

SetTerm sets the coefficient for a term a.i within a Polynomial. For i=0, sets the constant term.

func (Polynomial) String

func (p Polynomial) String() string

String creates a readable string representation for a Polynomial. Uses internal variable representations x.<n> where n corresponds to the variable's real life ID.

func (Polynomial) Subtract

func (p Polynomial) Subtract(p2 Polynomial, destructive bool) Polynomial

Subtract subtracts two Polynomials. Returns a new Polynomial, except when the 'destructive'-flag is set (then p is altered).

func (Polynomial) TraceString

func (p Polynomial) TraceString(resolv VariableResolver) string

TraceString creates a string representation for a Polynomial. Uses a variable name resolver to print 'real' variable identifiers. If no resolver is present, variables are printed in a generic form: +/- a.i x.i, where i is the position of the term. Coefficients are rounded to the 3rd place.

func (Polynomial) Zap

func (p Polynomial) Zap() Polynomial

Zap eliminates all terms with coefficient=0 from a polynomial.

type VariableResolver

type VariableResolver interface {
	GetVariableName(int) string     // get real-life name of x.i
	SetVariableSolved(int, float64) // message: x.i is solved
	IsCapsule(int) bool             // x.i has gone out of scope
}

A VariableResolver links to variables. We use an interface to resolve "real" variable names. Within the LEQ variables are encoded by their serial ID, which is used as their position within polynomias. Example: variable "n[3].a" with ID=4711 will become x.4711 internally. The resolver maps x.4711 ⟼ "n[3].a", i.e., IDs to names.

type X

type X struct {
	I int     // exponent of x
	C float64 // coeffiencet
}

X is a helper for quick construction of polynomials. It denotes a term

C⋅x[I]

I > 0