integer

package module
v0.0.2-0...-4fc1d00 Latest Latest
Warning

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

Go to latest
Published: Apr 16, 2021 License: CC0-1.0 Imports: 18 Imported by: 3

Documentation

Overview

Notes for the programmer: ------------------------- The underlying value describing an *Element will be an int64 when possible; otherwise it will be a *big.Int. You should attempt to gain the performance boost of using int64 versions of your computations when possible. Typical code will branch into two cases:

if x.IsInt64() {
	n := x.int64()	// Expose the underlying int64
	...
} else {
	n := x.bigInt()	// Expose the underlying *big.Int
	...
}

Take care not to modify the *big.Int returned by x.bigInt(), as this will modify the corresponding *Element (thus breaking our contract of immutability). Similarly, do not allow this *big.Int to escape into user-land.

The implementation attempts to guarantee that there is a unique 0 and 1 *Element element, returned via the functions Zero() and One(). However this isn't completely true: following good Go standard, a nil *Element behaves identically to 0. Furthermore, there's nothing stoping a user from writing:

x := &integers.Element{}

and thus creating a new, distinct 0. Care must be taken when adding new package functions: you should use the methods x.IsZero() and x.IsOne(). It's good practice to try to reuse Zero() and One(), rather than allowing additional copies of 0 or 1 to leak out of the package. The easiest way to ensure this is to use FromInt64(n) and fromBigIntAndReuse(n) to convert your working value into a *Element suitable for returning to the user.

Performance-wise, the biggest issue is big.Int.Mul(x,y), when x and y are large. Here Magma vastly outperforms big.Int. A quick search on the web shows that there exist several different algorithms for computing x * y, with different performance characteristics that depend on the size of x and y. Implementing these different algorithms, and modifying big.Int so that it uses the appropriate algorithm in each case, is a clear future task.

Index

Constants

View Source
const (
	ErrArgNotAnIntegerGreaterThan1 = objectError(iota)
	ErrArgsNotCoprime
	ErrArg1NotAnInteger
	ErrArg2NotAnInteger
	ErrArgNotAnInteger
	ErrArgOutOfRange
	ErrDivisionByZero
	ErrDecodingIntoNilObject
	ErrDecodingIntoExistingObject
	ErrEmptySlice
	ErrIllegalNegativeArg
	ErrIteratorIsClosed
	ErrIllegalNegativeExponent
	ErrIllegalZeroArg
	ErrOutOfRange
	ErrSliceNotCoprime
	ErrSliceLengthNotEqual
	ErrSliceNotPositive
	ErrStringNotAnInteger
)

Common errors.

Variables

View Source
var DefaultNumberOfMillerRabinTests = 10

DefaultNumberOfMillerRabinTests is the default number of Miller--Rabin tests when doing probabilistic primality testing in IsPrime(). This is only relevant for n such that |n| >= 2^63 - 1.

Functions

func AreCoprime

func AreCoprime(a *Element, b *Element) bool

AreCoprime returns true iff a and b are coprime.

func AreEqual

func AreEqual(x *Element, y *Element) bool

AreEqual returns true iff x equals y.

func Cmp

func Cmp(x *Element, y *Element) int

Cmp returns -1 if x < y, 0 if x == y, and +1 if x > y.

func IsPrime

func IsPrime(n *Element) bool

IsPrime runs primality tests on the absolute value |n| of n, returning true if they pass and false if they fail. A return value of false guarantees that n is composite. A return value of true guarantees that |n| is prime if |n| < 3,317,044,064,679,887,385,961,981. For larger |n| a return value of true indicates that |n| has a high probability of being prime.

func IsPrimeInt64

func IsPrimeInt64(n int64) bool

IsPrimeInt64 returns true iff the absolute value |n| is a prime.

func IsPrimePowerInt64

func IsPrimePowerInt64(n int64) (ok bool, p int64, k int64, err error)

IsPrimePowerInt64 tests whether the integer n is equal to p^k for some prime p. If n < 2 this returns an error.

func IsProbablyPrime

func IsProbablyPrime(n *Element, N int) bool

IsProbablyPrime returns false if n is definitely composite and returns true if the absolute value |n| of n has a high probability of being prime. It uses the ProbablyPrime() function from the Go big library, so per the documentation performs N Miller--Rabin tests.

func IsSliceCoprime

func IsSliceCoprime(as []*Element) (bool, error)

IsSliceCoprime returns true iff the elements of the slice are coprime.

func IsSlicePairwiseCoprime

func IsSlicePairwiseCoprime(as []*Element) (bool, error)

IsSlicePairwiseCoprime returns true iff the elements of the slice are pairwise coprime.

func NextPrimeInt64

func NextPrimeInt64(n int64) (int64, error)

NextPrimeInt64 returns the smallest prime number > |n| if this fits in an int64, and returns an error otherwise

func NthPrimeInt64

func NthPrimeInt64(N int64) (int64, error)

NthPrimeInt64 returns the N-th prime p if 1 <= N <= 2^17, or an error if N is out of range. Note that primes are indexed from 1.

func PrimeFactorsInt64

func PrimeFactorsInt64(n int64) ([]int64, error)

PrimeFactorsInt64 returns the prime factors of |n| as a sorted slice. It returns an error if and only if n is zero.

func QuotientAndRemainder

func QuotientAndRemainder(x *Element, y *Element) (*Element, *Element, error)

QuotientAndRemainder returns the quotient and remainder of x on division by y. This will return an error if y is zero.

func SetBigInt

func SetBigInt(n *big.Int, m *Element) *big.Int

SetBigInt sets the given *big.Int n to the value of the given integer m. Returns the *big.Int n.

func SliceToInt64Slice

func SliceToInt64Slice(S []*Element) ([]int64, error)

SliceToInt64Slice attempts to convert the given slice of integers to a slice of int64s. Returns the new slice on success.

func SliceToUint64Slice

func SliceToUint64Slice(S []*Element) ([]uint64, error)

SliceToUint64Slice attempts to convert the given slice of integers to a slice of uint64s. Returns the new slice on success.

func XGCDOfPair

func XGCDOfPair(a *Element, b *Element) (gcd *Element, u *Element, v *Element)

XGCDOfPair returns the greatest common divisor of a and b, along with integers u and v such that u a + v b = gcd. The gcd is always non-negative. The gcd of 0 and n is defined to be |n| (in particular, the gcd of 0 and 0 is 0).

Types

type CRTFunc

type CRTFunc func(residues ...*Element) (*Element, error)

CRTFunc applies the Chinese Remainder Theorem to the given residues. If the number of residues does not match the number of moduli then an error is returned.

func PrepareChineseRemainderTheorem

func PrepareChineseRemainderTheorem(moduli ...*Element) (CRTFunc, error)

PrepareChineseRemainderTheorem returns a function f that applies the Chinese Remainder Theorem to residues a_1,...,a_k. More precisely, f(a_1,...,a_k) returns the unique non-negative integer a such that 0 <= a < N and, for each i, n is congruent to a_i mod n_i, where the moduli are n_1,...,n_k, and N = n_1*...*n_k. The n_i must be positive and pairwise coprime.

type Element

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

Element is an element of the ring of integers.

func Add

func Add(x *Element, y *Element) *Element

Add returns x + y.

func AddInt64

func AddInt64(x int64, y *Element) *Element

AddInt64 returns x + y.

func Binomial

func Binomial(n *Element, k *Element) *Element

Binomial return the binomial coefficient of n \choose k. By convention this returns zero if either n or k are negative.

func BinomialInt64

func BinomialInt64(n int64, k int64) *Element

BinomialInt64 return the binomial coefficient of n \choose k. By convention this returns zero if either n or k are negative.

func ChineseRemainderTheorem

func ChineseRemainderTheorem(residues []*Element, moduli []*Element) (*Element, error)

ChineseRemainderTheorem returns the unique non-negative integer a such that 0 <= a < N and, for each i, a is congruent to a_i mod n_i, where residues = [a_1,...,a_k], moduli = [n_1,...,n_k], and N = n_1*...*n_k. The n_i must be positive and pairwise coprime.

func CommonPrimeFactors

func CommonPrimeFactors(a *Element, b *Element) []*Element

CommonPrimeFactors returns the common prime factors of a and b as a sorted slice of *Elements.

func CopySlice

func CopySlice(S []*Element) []*Element

CopySlice returns a copy of the slice S. The capacity will be preserved.

func Divisors

func Divisors(n *Element) ([]*Element, error)

Divisors returns the divisors of a non-zero integer n as a sorted slice of *Elements.

func DotProduct

func DotProduct(S1 []*Element, S2 []*Element) *Element

DotProduct returns the dot-product of the slices S1 and S2. That is, it returns S1[0] * S2[0] + ... + S1[k] * S2[k], where k+1 is the minimum of len(S1) and len(S2). The dot-product of two empty slices is the zero element.

func Factorial

func Factorial(n *Element) (*Element, error)

Factorial returns the value n!, for a non-negative value of n. By convention 0! is 1.

func FactorialInt64

func FactorialInt64(n int64) (*Element, error)

FactorialInt64 returns the value n!, for a non-negative value of n. By convention 0! is 1.

func FromBigInt

func FromBigInt(n *big.Int) *Element

FromBigInt returns a *Element with value n.

func FromInt

func FromInt(n int) *Element

FromInt returns n as an integer.

func FromInt32

func FromInt32(n int32) *Element

FromInt32 returns n as an integer.

func FromInt64

func FromInt64(n int64) *Element

FromInt64 returns a *Element with value n.

func FromString

func FromString(s string) (*Element, error)

FromString returns the integer represented by the string s.

func FromUint64

func FromUint64(n uint64) *Element

FromUint64 returns a *Element with value n.

func GCD

func GCD(ai ...*Element) *Element

GCD returns the greatest common divisor of a1, a2, ..., ak. The gcd is always non-negative. The gcd of 0 and n is defined to be |n| (in particular, the gcd of 0 is 0, and the gcd of the empty sequence is 0).

func GCDOfPair

func GCDOfPair(a *Element, b *Element) *Element

GCDOfPair returns the greatest common divisor of a and b. The gcd is always non-negative. The gcd of 0 and n is defined to be |n| (in particular, the gcd of 0 is 0). If you also require integers u and v such that u a + v y = gcd, then use XGCDOfPair.

func GobDecode

func GobDecode(dec *gob.Decoder) (*Element, error)

GobDecode reads the next value from the given gob.Decoder and decodes it as an integer.

func GobDecodeSlice

func GobDecodeSlice(dec *gob.Decoder) ([]*Element, error)

GobDecodeSlice reads the next value from the given gob.Decoder and decodes it as a slice of integers.

func IsMersenneNumber

func IsMersenneNumber(k *Element) (bool, *Element)

IsMersenneNumber returns true iff k = 2^n - 1 for some non-negative integer n. If true, also returns n.

func LCM

func LCM(a *Element, b *Element) *Element

LCM returns the least common multiple of a and b.

func Max

func Max(S ...*Element) (*Element, error)

Max returns the maximum element in the slice S. If S is empty then an error is returned.

func MaxAndIndex

func MaxAndIndex(S []*Element) (*Element, int, error)

MaxAndIndex returns the maximum element in the slice S, along with the index of the first occurrence of that element in S. If S is empty then an error is returned.

func MaxOfPair

func MaxOfPair(x *Element, y *Element) *Element

MaxOfPair returns the maximum element of x and y.

func Min

func Min(S ...*Element) (*Element, error)

Min returns the minimum element in the slice S. If S is empty then an error is returned.

func MinAndIndex

func MinAndIndex(S []*Element) (*Element, int, error)

MinAndIndex returns the minimum element in the slice S, along with the index of the first occurrence of that element in S. If S is empty then an error is returned.

func MinOfPair

func MinOfPair(x *Element, y *Element) *Element

MinOfPair returns the minimum element of x and y.

func Multiply

func Multiply(x *Element, y *Element) *Element

Multiply returns the product x * y.

func MultiplyByInt64ThenAdd

func MultiplyByInt64ThenAdd(a int64, b *Element, c *Element) *Element

MultiplyByInt64ThenAdd returns the value a * b + c.

func MultiplyMultiplyThenAdd

func MultiplyMultiplyThenAdd(a *Element, b *Element, c *Element, d *Element) *Element

MultiplyMultiplyThenAdd returns the value a * b + c * d.

func MultiplyMultiplyThenSubtract

func MultiplyMultiplyThenSubtract(a *Element, b *Element, c *Element, d *Element) *Element

MultiplyMultiplyThenSubtract returns the value a * b - c * d.

func MultiplyThenAdd

func MultiplyThenAdd(a *Element, b *Element, c *Element) *Element

MultiplyThenAdd returns the value a * b + c.

func MultiplyThenSubtract

func MultiplyThenSubtract(a *Element, b *Element, c *Element) *Element

MultiplyThenSubtract returns the value a * b - c.

func Negate

func Negate(n *Element) *Element

Negate returns -n.

func NextPrime

func NextPrime(n *Element) *Element

NextPrime returns the smallest prime number > |n|. Primality testing is done by IsPrime, which in particular is probabilistic for large values.

func NthPrime

func NthPrime(N int64) (*Element, error)

NthPrime returns the N-th prime p if 1 <= N <= 2^17, or an error if N is out of range. Note that primes are indexed from 1.

func One

func One() *Element

One returns 1.

func Power

func Power(n *Element, k *Element) (*Element, error)

Power returns n^k.

func PowerInt64

func PowerInt64(n *Element, k int64) (*Element, error)

PowerInt64 returns n^k.

func PrimeFactors

func PrimeFactors(n *Element) ([]*Element, error)

PrimeFactors returns the prime factors of |n| as a sorted slice. It returns an error if and only if n is zero. Primality testing is done by the IsPrime function, which in particular is probabilistic for large arguments.

func Product

func Product(S ...*Element) *Element

Product returns the product of the elements in the slice S. The product of the empty slice is one.

func ProductOfRange

func ProductOfRange(x1 *Element, x2 *Element) *Element

ProductOfRange returns the product of the elements x1 * (x1 + 1) * ... * x2. If x1 > x2 then ProductOfRange returns one.

func ProductOfRangeInt64

func ProductOfRangeInt64(x1 int64, x2 int64) *Element

ProductOfRangeInt64 returns the product of the elements x1 * (x1 + 1) * ... * x2. If x1 > x2 then ProductOfRange returns one.

func Quotient

func Quotient(x *Element, y *Element) (*Element, error)

Quotient returns the quotient of x on division by y. This will return an error if y is zero.

func Random

func Random(max *Element) *Element

Random returns a random integer in the range [0,max]. It will panic if max is negative. This wraps crypto/rand.

func ReverseSlice

func ReverseSlice(S []*Element) []*Element

ReverseSlice returns a new slice whose entries are equal to the entries of S, but in the reverse order.

func SliceFromInt32Slice

func SliceFromInt32Slice(S []int32) []*Element

SliceFromInt32Slice returns a slice of integers given by the slice S.

func SliceFromInt64Slice

func SliceFromInt64Slice(S []int64) []*Element

SliceFromInt64Slice returns a slice of integers given by the slice S.

func SliceFromIntSlice

func SliceFromIntSlice(S []int) []*Element

SliceFromIntSlice returns a slice of integers given by the slice S.

func SliceFromString

func SliceFromString(str string) ([]*Element, error)

SliceFromString converts a string into a slice of integers.

func SliceFromUint64Slice

func SliceFromUint64Slice(S []uint64) []*Element

SliceFromUint64Slice returns a slice of integers given by the slice S.

func Sort

func Sort(S []*Element) []*Element

Sort non-destructively sorts the given slice of integers. The sorted slice is returned.

func Subtract

func Subtract(x *Element, y *Element) *Element

Subtract returns x - y.

func Sum

func Sum(S ...*Element) *Element

Sum returns the sum of the elements in the slice S. The sum of the empty slice is the zero element.

func ToElement

func ToElement(x object.Element) (*Element, error)

ToElement attempts to convert the given object.Element to an integer. If x satisfies either of the interfaces:

type ToIntegerer interface {
	ToInteger() (*Element, error) // ToInteger attempts to convert the
	   object.Element to an integer.
}

type ToIntegererNoError interface {
	ToInteger() *Element // ToInteger converts the object.Element to an
	   integer.
}

then x's ToInteger method will be called.

func UniqueCommonPrimeFactors

func UniqueCommonPrimeFactors(a *Element, b *Element) []*Element

UniqueCommonPrimeFactors returns the common prime factors of a and b as a sorted slice of *Elements, without repeats.

func UniquePrimeFactors

func UniquePrimeFactors(n *Element) ([]*Element, error)

UniquePrimeFactors returns the prime factors of a non-zero integer n as a sorted slice of *Elements, without repeats, or an error if n is zero.

func Zero

func Zero() *Element

Zero returns 0.

func ZeroSlice

func ZeroSlice(n int) []*Element

ZeroSlice returns a slice of length n populated with the zero element.

func (*Element) Abs

func (n *Element) Abs() *Element

Abs returns the absolute value of n.

func (*Element) BigInt

func (n *Element) BigInt() *big.Int

BigInt returns the integer as a *big.Int.

func (*Element) Decrement

func (n *Element) Decrement() *Element

Decrement returns n - 1.

func (*Element) Divisors

func (n *Element) Divisors() ([]*Element, error)

Divisors returns the divisors of n as a sorted slice of *Elements.

func (*Element) GobDecode

func (n *Element) GobDecode(buf []byte) error

GobDecode implements the gob.GobDecoder interface. Important: Take great care that you are decoding into a new *Element; the safe way to do this is to use the GobDecode(dec *gob.Decode) function.

func (*Element) GobEncode

func (n *Element) GobEncode() ([]byte, error)

GobEncode implements the gob.GobEncoder interface.

func (*Element) Hash

func (n *Element) Hash() uint32

Hash returns a hash value for the given integer.

func (*Element) Increment

func (n *Element) Increment() *Element

Increment returns n + 1.

func (*Element) Int64

func (n *Element) Int64() (int64, error)

Int64 returns the integer as an int64.

func (*Element) InverseMod

func (n *Element) InverseMod(m *Element) (*Element, error)

InverseMod returns an inverse of n modulo m if n and m are coprime, and an error otherwise. The returned inverse modulo m is in the range 0 < n^{-1} < m if m is positive, and m < n^{-1} < 0 if m is negative.

func (*Element) IsDivisibleBy

func (n *Element) IsDivisibleBy(m *Element) (bool, error)

IsDivisibleBy returns true iff n is divisible by m and m is non-zero. If m is zero then an error is returned.

func (*Element) IsEqualTo

func (n *Element) IsEqualTo(m *Element) bool

IsEqualTo returns true iff n = m.

func (*Element) IsEqualToInt

func (n *Element) IsEqualToInt(m int) bool

IsEqualToInt returns true iff n = m.

func (*Element) IsEqualToInt64

func (n *Element) IsEqualToInt64(m int64) bool

IsEqualToInt64 returns true iff n = m.

func (*Element) IsEqualToUint64

func (n *Element) IsEqualToUint64(m uint64) bool

IsEqualToUint64 returns true iff n = m.

func (*Element) IsEven

func (n *Element) IsEven() bool

IsEven returns true iff n is even.

func (*Element) IsGreaterThan

func (n *Element) IsGreaterThan(m *Element) bool

IsGreaterThan returns true iff n > m.

func (*Element) IsGreaterThanInt64

func (n *Element) IsGreaterThanInt64(m int64) bool

IsGreaterThanInt64 returns true iff n > m.

func (*Element) IsGreaterThanOrEqualTo

func (n *Element) IsGreaterThanOrEqualTo(m *Element) bool

IsGreaterThanOrEqualTo returns true iff n >= m.

func (*Element) IsGreaterThanOrEqualToInt64

func (n *Element) IsGreaterThanOrEqualToInt64(m int64) bool

IsGreaterThanOrEqualToInt64 returns true iff n >= m.

func (*Element) IsInt64

func (n *Element) IsInt64() bool

IsInt64 returns true iff the integer can be expressed as an int64.

func (*Element) IsLessThan

func (n *Element) IsLessThan(m *Element) bool

IsLessThan returns true iff n < m.

func (*Element) IsLessThanInt64

func (n *Element) IsLessThanInt64(m int64) bool

IsLessThanInt64 returns true iff n < m.

func (*Element) IsLessThanOrEqualTo

func (n *Element) IsLessThanOrEqualTo(m *Element) bool

IsLessThanOrEqualTo returns true iff n <= m.

func (*Element) IsLessThanOrEqualToInt64

func (n *Element) IsLessThanOrEqualToInt64(m int64) bool

IsLessThanOrEqualToInt64 returns true iff n <= m.

func (*Element) IsNegative

func (n *Element) IsNegative() bool

IsNegative returns true iff n < 0.

func (*Element) IsOdd

func (n *Element) IsOdd() bool

IsOdd returns true iff n is odd.

func (*Element) IsOne

func (n *Element) IsOne() bool

IsOne returns true iff n is 1.

func (*Element) IsPositive

func (n *Element) IsPositive() bool

IsPositive returns true iff n > 0.

func (*Element) IsPrime

func (n *Element) IsPrime() bool

IsPrime runs primality tests on the absolute value |n| of n, returning true if they pass and false if they fail. A return value of false guarantees that n is composite. A return value of true guarantees that |n| is prime if |n| < 3,317,044,064,679,887,385,961,981. For larger |n| a return value of true indicates that |n| has a high probability of being prime.

func (*Element) IsUint64

func (n *Element) IsUint64() bool

IsUint64 returns true iff the integer can be expressed as a uint64.

func (*Element) IsZero

func (n *Element) IsZero() bool

IsZero returns true iff n is 0.

func (*Element) Mod

func (n *Element) Mod(m *Element) (*Element, error)

Mod returns n modulo m if m is non-zero, and an error otherwise. The returned modulus k is in the range 0 <= k < m if m is positive, and m < k <= 0 if m is negative.

func (*Element) ModInt64

func (n *Element) ModInt64(m int64) (int64, error)

ModInt64 returns n modulo m if m is non-zero, and an error otherwise. The returned modulus k is in the range 0 <= k < m if m is positive, and m < k <= 0 if m is negative.

func (*Element) Negate

func (n *Element) Negate() *Element

Negate return -n.

func (*Element) Parent

func (n *Element) Parent() object.Parent

Parent returns the ring of integers as a object.Parent. This can safely be coerced to type Parent.

func (*Element) Power

func (n *Element) Power(k *Element) (*Element, error)

Power returns n^k.

func (*Element) PowerInt64

func (n *Element) PowerInt64(k int64) (*Element, error)

PowerInt64 returns n^k.

func (*Element) PrimeFactors

func (n *Element) PrimeFactors() ([]*Element, error)

PrimeFactors returns the prime factors of n as a sorted slice of *Elements.

func (*Element) ScalarMultiplyByInt64

func (n *Element) ScalarMultiplyByInt64(a int64) *Element

ScalarMultiplyByInt64 returns the product a * n.

func (*Element) ScalarMultiplyByInteger

func (n *Element) ScalarMultiplyByInteger(a *Element) *Element

ScalarMultiplyByInteger returns the product a * n.

func (*Element) ScalarMultiplyByUint64

func (n *Element) ScalarMultiplyByUint64(a uint64) *Element

ScalarMultiplyByUint64 returns the product a * n.

func (*Element) Sign

func (n *Element) Sign() int

Sign returns the sign of n, i.e. -1 if n < 0; 0 if n == 0; +1 if n > 0.

func (*Element) String

func (n *Element) String() string

String returns a string representation of the given integer.

func (*Element) ToInteger

func (n *Element) ToInteger() (*Element, error)

ToInteger returns n.

func (*Element) Uint64

func (n *Element) Uint64() (uint64, error)

Uint64 returns the integer as a uint64.

func (*Element) UniquePrimeFactors

func (n *Element) UniquePrimeFactors() ([]*Element, error)

UniquePrimeFactors returns the prime factors of n as a sorted slice of *Elements, without repeats.

type Int32Slice

type Int32Slice []int32

Int32Slice wraps an []int32, implementing slice.Interface and returning the entries as *Elements.

func (Int32Slice) Entry

func (S Int32Slice) Entry(i int) object.Element

Entry returns the i-th element in the slice. This will panic if i is out of range.

func (Int32Slice) Hash

func (S Int32Slice) Hash() uint32

Hash returns a hash value for this slice.

func (Int32Slice) Len

func (S Int32Slice) Len() int

Len returns the length of the slice.

func (Int32Slice) Slice

func (S Int32Slice) Slice(k int, m int) slice.Interface

Slice returns a subslice starting at index k and of length m - k. The returned subslice will be of the same underlying type. This will panic if the arguments are out of range.

type Int64Slice

type Int64Slice []int64

Int64Slice wraps an []int64, implementing slice.Interface and returning the entries as *Elements.

func (Int64Slice) Entry

func (S Int64Slice) Entry(i int) object.Element

Entry returns the i-th element in the slice. This will panic if i is out of range.

func (Int64Slice) Hash

func (S Int64Slice) Hash() uint32

Hash returns a hash value for this slice.

func (Int64Slice) Len

func (S Int64Slice) Len() int

Len returns the length of the slice.

func (Int64Slice) Slice

func (S Int64Slice) Slice(k int, m int) slice.Interface

Slice returns a subslice starting at index k and of length m - k. The returned subslice will be of the same underlying type. This will panic if the arguments are out of range.

type IntSlice

type IntSlice []int

IntSlice wraps an []int, implementing slice.Interface and returning the entries as *Elements.

func (IntSlice) Entry

func (S IntSlice) Entry(i int) object.Element

Entry returns the i-th element in the slice. This will panic if i is out of range.

func (IntSlice) Hash

func (S IntSlice) Hash() uint32

Hash returns a hash value for this slice.

func (IntSlice) Len

func (S IntSlice) Len() int

Len returns the length of the slice.

func (IntSlice) Slice

func (S IntSlice) Slice(k int, m int) slice.Interface

Slice returns a subslice starting at index k and of length m - k. The returned subslice will be of the same underlying type. This will panic if the arguments are out of range.

type Parent

type Parent struct{}

Parent represents the (unique) ring of integers.

func Ring

func Ring() Parent

Ring returns the (unique) ring of integers.

func (Parent) Add

Add returns x + y.

func (Parent) AreEqual

func (R Parent) AreEqual(x object.Element, y object.Element) (bool, error)

AreEqual returns true iff x equals y.

func (Parent) Cmp

func (R Parent) Cmp(x object.Element, y object.Element) (int, error)

Cmp returns -1 if x < y, 0 if x == y, and +1 if x > y.

func (Parent) Contains

func (R Parent) Contains(x object.Element) bool

Contains returns true iff x is an integer, or can naturally be regarded as an integer.

func (Parent) DotProduct

func (R Parent) DotProduct(S1 []object.Element, S2 []object.Element) (object.Element, error)

DotProduct returns the dot-product of the slices S1 and S2. That is, it returns S1[0] * S2[0] + ... + S1[k] * S2[k], where k+1 is the minimum of len(S1) and len(S2). The dot-product of two empty slices is the zero element.

func (Parent) FromInteger

func (R Parent) FromInteger(n *Element) object.Element

FromInteger returns n.

func (Parent) IsOne

func (R Parent) IsOne(x object.Element) (bool, error)

IsOne returns true iff x is the integer 1.

func (Parent) IsUnit

func (R Parent) IsUnit(x object.Element) (bool, object.Element, error)

IsUnit returns true iff x is a multiplicative unit in the ring of integers (i.e. x = 1 or -1). If true, also returns the inverse element y such that x * y = 1.

func (Parent) IsZero

func (R Parent) IsZero(x object.Element) (bool, error)

IsZero returns true iff x is the integer 0.

func (Parent) Max

func (R Parent) Max(S ...object.Element) (object.Element, error)

Max returns the maximum element in the slice S. If S is empty then an error is returned.

func (Parent) MaxAndIndex

func (R Parent) MaxAndIndex(S []object.Element) (object.Element, int, error)

MaxAndIndex returns the maximum element in the slice S, along with the index of the first occurrence of that element in S. If S is empty then an error is returned.

func (Parent) Min

func (R Parent) Min(S ...object.Element) (object.Element, error)

Min returns the maximum element in the slice S. If S is empty then an error is returned.

func (Parent) MinAndIndex

func (R Parent) MinAndIndex(S []object.Element) (object.Element, int, error)

MinAndIndex returns the minimum element in the slice S, along with the index of the first occurrence of that element in S. If S is empty then an error is returned.

func (Parent) Multiply

func (R Parent) Multiply(x object.Element, y object.Element) (object.Element, error)

Multiply returns the product x * y.

func (Parent) Negate

func (R Parent) Negate(x object.Element) (object.Element, error)

Negate returns -x.

func (Parent) One

func (R Parent) One() object.Element

One returns 1.

func (Parent) Power

func (R Parent) Power(x object.Element, k *Element) (object.Element, error)

Power returns x^k, where k is a non-negative integer.

func (Parent) Product

func (R Parent) Product(S ...object.Element) (object.Element, error)

Product returns the product of the elements in the slice S. The product of the empty slice is one.

func (Parent) ScalarMultiplyByInteger

func (R Parent) ScalarMultiplyByInteger(n *Element, x object.Element) (object.Element, error)

ScalarMultiplyByInteger returns nx, where this is defined to be x + ... + x (n times) if n is positive, and -x - ... - x (|n| times) if n is negative.

func (Parent) Sort

func (R Parent) Sort(S []object.Element) ([]object.Element, error)

Sort non-destructively sorts the given slice of integers. The sorted slice is returned.

func (Parent) String

func (R Parent) String() string

String returns a string representation of the ring of integers.

func (Parent) Subtract

func (R Parent) Subtract(x object.Element, y object.Element) (object.Element, error)

Subtract returns x - y.

func (Parent) Sum

func (R Parent) Sum(S ...object.Element) (object.Element, error)

Sum returns the sum of the elements in the slice S. The sum of the empty slice is the zero element.

func (Parent) ToElement

func (R Parent) ToElement(x object.Element) (object.Element, error)

ToElement returns x as an element of this parent, or an error if x cannot naturally be regarded as an element of this parent.

func (Parent) Zero

func (R Parent) Zero() object.Element

Zero returns 0.

type PrimeIteratorInt64

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

PrimeIteratorInt64 provides an efficient way to iterate over the primes that fit in an int64.

func NewPrimeIteratorInt64

func NewPrimeIteratorInt64(n int64) *PrimeIteratorInt64

NewPrimeIteratorInt64 returns a new prime iterator starting at the smallest prime number > |n|.

func (*PrimeIteratorInt64) Close

func (np *PrimeIteratorInt64) Close() error

Close stops the iterator.

func (*PrimeIteratorInt64) Next

func (np *PrimeIteratorInt64) Next() (int64, error)

Next returns the next prime from the iterator, or an error.

type Slice

type Slice []*Element

Slice wraps an []*Element, implementing slice.Interface.

func (Slice) Entry

func (S Slice) Entry(i int) object.Element

Entry returns the i-th element in the slice. This will panic if i is out of range.

func (Slice) Hash

func (S Slice) Hash() uint32

Hash returns a hash value for this slice.

func (Slice) Len

func (S Slice) Len() int

Len returns the length of the slice.

func (Slice) Slice

func (S Slice) Slice(k int, m int) slice.Interface

Slice returns a subslice starting at index k and of length m - k. The returned subslice will be of the same underlying type. This will panic if the arguments are out of range.

type SortableSlice

type SortableSlice []*Element

SortableSlice implements slice.Interface and sort.Interface.

func (SortableSlice) Entry

func (S SortableSlice) Entry(i int) object.Element

Entry returns the i-th element in the slice. This will panic if i is out of range.

func (SortableSlice) Hash

func (S SortableSlice) Hash() uint32

Hash returns a hash value for this slice.

func (SortableSlice) Len

func (S SortableSlice) Len() int

Len returns the length of the slice.

func (SortableSlice) Less

func (S SortableSlice) Less(i int, j int) bool

Less reports whether the element with index i should sort before the element with index j.

func (SortableSlice) Sort

func (S SortableSlice) Sort()

Sort sorts the slice in place.

func (SortableSlice) Swap

func (S SortableSlice) Swap(i int, j int)

Swap swaps the elements with indexes i and j.

type Uint64Slice

type Uint64Slice []uint64

Uint64Slice wraps an []uint64, implementing slice.Interface and returning the entries as *Elements.

func (Uint64Slice) Entry

func (S Uint64Slice) Entry(i int) object.Element

Entry returns the i-th element in the slice. This will panic if i is out of range.

func (Uint64Slice) Hash

func (S Uint64Slice) Hash() uint32

Hash returns a hash value for this slice.

func (Uint64Slice) Len

func (S Uint64Slice) Len() int

Len returns the length of the slice.

func (Uint64Slice) Slice

func (S Uint64Slice) Slice(k int, m int) slice.Interface

Slice returns a subslice starting at index k and of length m - k. The returned subslice will be of the same underlying type. This will panic if the arguments are out of range.

Directories

Path Synopsis
internal

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL