integer

package
v0.0.2-0...-db6250e Latest Latest
Warning

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

 Go to latest Published: Dec 17, 2020 License: CC0-1.0, CC0-1.0 Imports: 20 Imported by: 6

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

This section is empty.

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() hash.Value

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() hash.Value

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() hash.Value

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() hash.Value

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 

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

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() hash.Value

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() hash.Value

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() hash.Value

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.

Source Files

View all Source files

Directories

Path Synopsis
internal
bigintfactory

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.