Documentation
¶
Overview ¶
Copyright Consensys Software Inc.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
SPDX-License-Identifier: Apache-2.0
Copyright Consensys Software Inc.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
SPDX-License-Identifier: Apache-2.0
Copyright Consensys Software Inc.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
SPDX-License-Identifier: Apache-2.0
Copyright Consensys Software Inc.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
SPDX-License-Identifier: Apache-2.0
Copyright Consensys Software Inc.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
SPDX-License-Identifier: Apache-2.0
Index ¶
- func Eval[S util.Comparable[S], T Term[S, T], P Polynomial[S, T, P]](poly P, env func(S) big.Int) *big.Int
- func Lisp[S util.Comparable[S], T Term[S, T], P Polynomial[S, T, P]](poly P, env func(S) string) sexp.SExp
- func String[S util.Comparable[S], T Term[S, T], P Polynomial[S, T, P]](poly P, env func(S) string) string
- type ArrayPoly
- func (p *ArrayPoly[S]) Add(other *ArrayPoly[S]) *ArrayPoly[S]
- func (p *ArrayPoly[S]) AddScalar(scalar *big.Int) *ArrayPoly[S]
- func (p *ArrayPoly[S]) AddTerm(other Monomial[S])
- func (p *ArrayPoly[S]) Clone() *ArrayPoly[S]
- func (p *ArrayPoly[S]) Cmp(other *ArrayPoly[S]) int
- func (p *ArrayPoly[S]) Const64(val uint64) *ArrayPoly[S]
- func (p *ArrayPoly[S]) Equal(other *ArrayPoly[S]) bool
- func (p *ArrayPoly[S]) IsZero() (res bool, ok bool)
- func (p *ArrayPoly[S]) Len() uint
- func (p *ArrayPoly[S]) Mul(other *ArrayPoly[S]) *ArrayPoly[S]
- func (p *ArrayPoly[S]) MulScalar(scalar *big.Int) *ArrayPoly[S]
- func (p *ArrayPoly[S]) Negate() *ArrayPoly[S]
- func (p *ArrayPoly[S]) Set(terms ...Monomial[S]) *ArrayPoly[S]
- func (p *ArrayPoly[S]) Shr(n uint) (*ArrayPoly[S], *ArrayPoly[S])
- func (p *ArrayPoly[S]) Signed() bool
- func (p *ArrayPoly[S]) Sub(other *ArrayPoly[S]) *ArrayPoly[S]
- func (p *ArrayPoly[S]) SubTerm(other Monomial[S])
- func (p *ArrayPoly[S]) Term(ith uint) Monomial[S]
- type Monomial
- func (p Monomial[S]) Clone() Monomial[S]
- func (p Monomial[S]) Cmp(other Monomial[S]) int
- func (p Monomial[S]) Coefficient() big.Int
- func (p Monomial[S]) Contains(v S) bool
- func (p Monomial[S]) Equal(other Monomial[S]) bool
- func (p Monomial[S]) FactorOut(v S) Monomial[S]
- func (p Monomial[S]) IsNegative() bool
- func (p Monomial[S]) IsZero() bool
- func (p Monomial[S]) Len() uint
- func (p Monomial[S]) Matches(other Monomial[S]) bool
- func (p Monomial[S]) Mul(other Monomial[S]) Monomial[S]
- func (p Monomial[S]) MulScalar(scalar *big.Int) Monomial[S]
- func (p Monomial[S]) Neg() Monomial[S]
- func (p Monomial[S]) Negate() Monomial[S]
- func (p Monomial[S]) Nth(index uint) S
- func (p Monomial[S]) Shr(n uint) (quot Monomial[S], rem Monomial[S])
- func (p Monomial[S]) String(env func(S) string) string
- func (p Monomial[S]) Vars() []S
- type Polynomial
- type Term
- type Var
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Eval ¶
func Eval[S util.Comparable[S], T Term[S, T], P Polynomial[S, T, P]](poly P, env func(S) big.Int) *big.Int
Eval evaluates a given polynomial with a given environment (i.e. mapping of variables to values)
func Lisp ¶
func Lisp[S util.Comparable[S], T Term[S, T], P Polynomial[S, T, P]](poly P, env func(S) string) sexp.SExp
Lisp constructs a suitable lisp representation for a given polynomial assuming an environment which maps identifiers to strings.
func String ¶
func String[S util.Comparable[S], T Term[S, T], P Polynomial[S, T, P]](poly P, env func(S) string) string
String constructs a suitable string representation for a given polynomial assuming an environment which maps identifiers to strings.
Types ¶
type ArrayPoly ¶
type ArrayPoly[S util.Comparable[S]] struct { // contains filtered or unexported fields }
ArrayPoly is the simpliest (and least efficient) polynomial implementation. It provides a reference against which other (more efficient) implementations can be compared. Observe that an unitialised ArrayPoly variable corresponds with zero.
func Parse ¶
func Parse(input string) (*ArrayPoly[Var], []source.SyntaxError)
Parse a given input string representing a polynomial, or produce one or more errors.
func (*ArrayPoly[S]) Equal ¶
Equal performs structural equality between two polynomials. That is, they are consider the same provide they have identical structure.
func (*ArrayPoly[S]) IsZero ¶
IsZero returns an indication as to whether this polynomial is equivalent to zero (or not). This is a three valued logic system which can return either "yes", "no" or "maybe" where: (i) "yes" means the polynomial always evaluates to zero; (ii) "no" means the polynomial never evaluates to zero; (iii) "maybe" indicates the polynomial may sometimes evaluate to zero. When the return ok holds then res indicates either yes or not. Otherwise, the result is maybe.
func (*ArrayPoly[S]) Signed ¶
Signed determines whether or not this polynomial can evaluate to both positive and negative values. Currently, this is defined simply as whether or not a contained monomial has a negative coefficient.
type Monomial ¶
type Monomial[S util.Comparable[S]] struct { // contains filtered or unexported fields }
Monomial represents a monomial within an array polynomial.
func NewMonomial ¶
func NewMonomial[S util.Comparable[S]](coefficient big.Int, vars ...S) Monomial[S]
NewMonomial constructs a new array term with a given coefficient and zero or more variables.
func (Monomial[S]) Coefficient ¶
Coefficient returns the coefficient of this term.
func (Monomial[S]) Contains ¶
Contains checks whether this monomial contains the given variable, or not.
func (Monomial[S]) Equal ¶
Equal performs structural equality between two mononomials. That is, they are consider the same provide they have identical structure.
func (Monomial[S]) FactorOut ¶
FactorOut produces a fresh monomial containing one less occurrence of the given variable (if it is contained within). Otherwise, it returns an identical monomial.
func (Monomial[S]) IsNegative ¶
IsNegative checks whether or not the coefficient for this monomial is negative.
func (Monomial[S]) IsZero ¶
IsZero checks whether or not this monomial is zero. Or, put another way, whether or not the coefficient of this monomial is zero.
func (Monomial[S]) Matches ¶
Matches determines whether or not the variables of this term match those of the other.
func (Monomial[S]) Mul ¶
Mul returns a fresh monomial representing the multiplication of this monomial and another.
type Polynomial ¶
type Polynomial[S util.Comparable[S], T Term[S, T], P any] interface { // Len returns the number of terms in this polynomial. Len() uint // Term returns the ith term in this polynomial. Term(uint) T // Initialise this polynomial from zero or more terms, returnining this. Set(...T) P // Initialise this polynomial from a 64bit constant. Const64(uint64) P // Cmp provides an ordering over polynomials. Cmp(o P) int // IsZero returns an indication as to whether this polynomial is equivalent // to zero (or not). This is a three valued logic system which can return // either "yes", "no" or "maybe" where: (i) "yes" means the polynomial // always evaluates to zero; (ii) "no" means the polynomial never evaluates // to zero; (iii) "maybe" indicates the polynomial may sometimes evaluate to // zero. When the return ok holds then res indicates either yes or not. // Otherwise, the result is maybe. IsZero() (res bool, ok bool) // Add another polynomial onto this polynomial, such that this polynomial is // updated in place. Add(P) P // Subtract another polynomial from this polynomial, such that this // polynomial is updated in place. Sub(P) P // Multiply this polynomial by another polynomial, such that this polynomial // is updated in place. Mul(P) P // Negate each mononial in this polynomial. Negate() P // For a given bitwidth n, divide a polynomial by 2^n produces a quotient and // remainder. For example, dividing 256*x1+x0 by 2^8 gives x1 remainder x0. // This algorithm is somehow akin to "shifting" a polynomial downwards. For // example, consider our example again: // // 15 8 7 0 // +----------------+-----------------+ // | 2^8*x1 | x0 | // +----------------+-----------------+ // // Then, shifting this down by 8bits gives: // // 7 0 // +-----------------+ // >>>>>>>>>>>>>>>> | x1 | // +-----------------+ // // And we are left with a remainder as well. Shr(n uint) (quot P, rem P) }
Polynomial represents a sum of terms of a type T of variables.
type Term ¶
type Term[S any, T any] interface { // Coefficient returns the coefficient of this term. Coefficient() big.Int // Len returns the number of variables in this polynomial term. Len() uint // Negate this term Negate() T // Nth returns the nth variable in this polynomial term. Nth(uint) S // Matches determines whether or not the variables of this term match those // of the other. Matches(other T) bool // Check whether this term has a negative coefficient (or not) IsNegative() bool }
Term represents a product (or monomial) within a polynomial.
Source Files