interval

package
Version: v0.2.0 Latest Latest
Warning

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

Go to latest
Published: Dec 19, 2019 License: Apache-2.0 Imports: 1 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type IntRange

type IntRange [2]*big.Int

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) Add

func (x IntRange) Add(y IntRange) (z IntRange)

Add returns z = x + y.

func (IntRange) And

func (x IntRange) And(y IntRange) (z IntRange)

And returns z = x & y.

func (IntRange) ContainsInt

func (x IntRange) ContainsInt(i *big.Int) bool

ContainsInt returns whether x contains i.

func (IntRange) ContainsIntRange

func (x IntRange) ContainsIntRange(y IntRange) bool

ContainsIntRange returns whether x contains every element of y.

It returns true if y is empty.

func (IntRange) ContainsNegative

func (x IntRange) ContainsNegative() bool

ContainsNegative returns whether x contains at least one negative value.

func (IntRange) ContainsNonNegative

func (x IntRange) ContainsNonNegative() bool

ContainsNonNegative returns whether x contains at least one non-negative value.

func (IntRange) ContainsPositive

func (x IntRange) ContainsPositive() bool

ContainsPositive returns whether x contains at least one positive value.

func (IntRange) ContainsZero

func (x IntRange) ContainsZero() bool

ContainsZero returns whether x contains zero.

func (IntRange) Empty

func (x IntRange) Empty() bool

Empty returns whether x is empty.

func (IntRange) Eq

func (x IntRange) Eq(y IntRange) bool

Eq returns whether x equals y.

func (IntRange) Intersect

func (x IntRange) Intersect(y IntRange) (z IntRange)

Intersect returns z = x ∩ y, the intersection of two intervals.

func (IntRange) Mul

func (x IntRange) Mul(y IntRange) (z IntRange)

Mul returns z = x * y.

func (IntRange) Or

func (x IntRange) Or(y IntRange) (z IntRange)

Or returns z = x | y.

func (IntRange) String

func (x IntRange) String() string

String returns a string representation of x.

func (IntRange) Sub

func (x IntRange) Sub(y IntRange) (z IntRange)

Sub returns z = x - y.

func (IntRange) TryAdd

func (x IntRange) TryAdd(y IntRange) (z IntRange, ok bool)

TryAdd returns (x.Add(y), true).

func (IntRange) TryAnd

func (x IntRange) TryAnd(y IntRange) (z IntRange, ok bool)

TryAnd returns (x.And(y), true).

func (IntRange) TryIntersect

func (x IntRange) TryIntersect(y IntRange) (z IntRange, ok bool)

TryIntersect returns (x.Intersect(y), true).

func (IntRange) TryLsh

func (x IntRange) TryLsh(y IntRange) (z IntRange, ok bool)

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) TryMul

func (x IntRange) TryMul(y IntRange) (z IntRange, ok bool)

TryMul returns (x.Mul(y), true).

func (IntRange) TryOr

func (x IntRange) TryOr(y IntRange) (z IntRange, ok bool)

TryOr returns (x.Or(y), true).

func (IntRange) TryQuo

func (x IntRange) TryQuo(y IntRange) (z IntRange, ok bool)

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

func (x IntRange) TryRsh(y IntRange) (z IntRange, ok bool)

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.

func (IntRange) TrySub

func (x IntRange) TrySub(y IntRange) (z IntRange, ok bool)

TrySub returns (x.Sub(y), true).

func (IntRange) TryUnite

func (x IntRange) TryUnite(y IntRange) (z IntRange, ok bool)

TryUnite returns (x.Unite(y), true).

func (IntRange) Unite

func (x IntRange) Unite(y IntRange) (z IntRange)

Unite returns z = x ∪ y, the union of two intervals.

Source Files

Jump to

Keyboard shortcuts

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