Documentation
¶
Overview ¶
Package interval provides interval arithmetic on big integers. Big means arbitrary-precision, as per the standard math/big package.
For example, if x is in the interval [3 ..= 6] and y is in the interval [10 ..= 15] then x+y is in the interval [13 ..= 21].
As in Rust, the [m ..= n] syntax means all integers i such that (m <= i) and (i <= n). Unlike Rust, neither bound can be omitted, but they may be infinite. For example, if x is in the interval [3 ..= +∞] and y is in the interval [-4 ..= -2], then x*y is in the interval [-∞ ..= -6].
As a motivating example, if a compiler knows that the integer-typed variables i and j are in the intervals [0 ..= 255] and [0 ..= 3], and that the array a has 1024 elements, then it can prove that the array-index expression a[4*i + j] is memory-safe without needing an at-runtime bounds check.
This package depends only on the standard math/big package.
Index ¶
- type IntRange
- func (x IntRange) Add(y IntRange) (z IntRange)
- func (x IntRange) And(y IntRange) (z IntRange)
- func (x IntRange) ContainsInt(i *big.Int) bool
- func (x IntRange) ContainsIntRange(y IntRange) bool
- func (x IntRange) ContainsNegative() bool
- func (x IntRange) ContainsNonNegative() bool
- func (x IntRange) ContainsPositive() bool
- func (x IntRange) ContainsZero() bool
- func (x IntRange) Empty() bool
- func (x IntRange) Eq(y IntRange) bool
- func (x IntRange) Intersect(y IntRange) (z IntRange)
- func (x IntRange) Mul(y IntRange) (z IntRange)
- func (x IntRange) Or(y IntRange) (z IntRange)
- func (x IntRange) String() string
- func (x IntRange) Sub(y IntRange) (z IntRange)
- func (x IntRange) TryAdd(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryAnd(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryIntersect(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryLsh(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryMul(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryOr(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryQuo(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryRsh(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TrySub(y IntRange) (z IntRange, ok bool)
- func (x IntRange) TryUnite(y IntRange) (z IntRange, ok bool)
- func (x IntRange) Unite(y IntRange) (z IntRange)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type IntRange ¶
IntRange is an integer interval. The array elements are the minimum and maximum values, inclusive (if non-nil) on both ends. A nil element means unbounded: negative or positive infinity.
The zero value (zero in the Go sense, not in the integer sense) is a valid, infinitely sized interval, unbounded at both ends.
IntRange's operator-like methods (Add, Mul, etc) return an IntRange whose *big.Int pointer values (if non-nil) are always distinct from its inputs' *big.Int pointer values. Specifically, after "z = x.Add(y)", mutating "*z[0]" will not affect "*x[0]", "*x[1]", "*y[0]" or "*y[1]".
Those operator-like methods come in two forms: Foo and TryFoo. The TryFoo forms return (z IntRange, ok bool). The bool indicates success, as operations like dividing by zero or shifting by a negative value can fail. When TryFoo can never fail, there is also a Foo method that omits the always-true bool. For example, there are Add, TryAdd and TryLsh methods, but no Lsh method.
A subtle point is that an interval's minimum or maximum can be infinite, but if an integer value i is known to be within such an interval, i's possible values are arbitrarily large but not infinite. Specifically, 0*i is unambiguously always equal to 0.
It is also valid for the first element to be greater than the second element. This represents an empty interval. There is more than one representation of an empty interval.
"Int" abbreviates "Integer" (the same as for big.Int), not "Interval". Similarly, we use "Range" instead of "Interval" to avoid unnecessary confusion, even though this type is indeed an integer interval.
func (IntRange) ContainsInt ¶
ContainsInt returns whether x contains i.
func (IntRange) ContainsIntRange ¶
ContainsIntRange returns whether x contains every element of y.
It returns true if y is empty.
func (IntRange) ContainsNegative ¶
ContainsNegative returns whether x contains at least one negative value.
func (IntRange) ContainsNonNegative ¶
ContainsNonNegative returns whether x contains at least one non-negative value.
func (IntRange) ContainsPositive ¶
ContainsPositive returns whether x contains at least one positive value.
func (IntRange) ContainsZero ¶
ContainsZero returns whether x contains zero.
func (IntRange) TryIntersect ¶
TryIntersect returns (x.Intersect(y), true).
func (IntRange) TryLsh ¶
TryLsh returns z = x << y.
ok is false (and z will be IntRange{nil, nil}) if x is non-empty and y contains at least one negative value, as it's invalid to shift by a negative number. Otherwise, ok is true.
func (IntRange) TryQuo ¶
TryQuo returns z = x / y. Like the big.Int.Quo method (and unlike the big.Int.Div method), it truncates towards zero.
ok is false (and z will be IntRange{nil, nil}) if x is non-empty and y contains zero, as it's invalid to divide by zero. Otherwise, ok is true.
func (IntRange) TryRsh ¶
TryRsh returns z = x >> y.
ok is false (and z will be IntRange{nil, nil}) if x is non-empty and y contains at least one negative value, as it's invalid to shift by a negative number. Otherwise, ok is true.
Source Files