bignum

package
v0.0.0-...-90c9d3a Latest Latest
Warning

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

 Go to latest Published: Mar 21, 2010 License: BSD-3-Clause, GooglePatentClause Imports: 2 Imported by: 0

Documentation

Overview

A package for arbitrary precision arithmethic. It implements the following numeric types:

  • Natural unsigned integers
  • Integer signed integers
  • Rational rational numbers

This package has been designed for ease of use but the functions it provides are likely to be quite slow. It may be deprecated eventually. Use package big instead, if possible.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Div128 

func Div128(x1, x0, y uint64) (q, r uint64)

q = (x1<<64 + x0)/y + r

func Iadd 

func Iadd(z, x, y *Integer)

Iadd sets z to the sum x + y. z must exist and may be x or y.

func Iscale 

func Iscale(z *Integer, d int64)

Nscale sets *z to the scaled value (*z) * d.

func Isub 

func Isub(z, x, y *Integer)

func Mul128 

func Mul128(x, y uint64) (z1, z0 uint64)

z1<<64 + z0 = x*y

func MulAdd128 

func MulAdd128(x, y, c uint64) (z1, z0 uint64)

z1<<64 + z0 = x*y + c

func Nadd 

func Nadd(zp *Natural, x, y Natural)

Nadd sets *zp to the sum x + y. *zp may be x or y.

func Nscale 

func Nscale(z *Natural, d uint64)

Nscale sets *z to the scaled value (*z) * d.

func Nsub 

func Nsub(zp *Natural, x, y Natural)

Nsub sets *zp to the difference x - y for x >= y. If x < y, an underflow run-time error occurs (use Cmp to test if x >= y). *zp may be x or y.

Types

type Integer 

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

Integer represents a signed integer value of arbitrary precision.

func Int 

func Int(x int64) *Integer

Int creates a small integer with value x.

func IntFromString 

func IntFromString(s string, base uint) (*Integer, uint, int)

IntFromString returns the integer corresponding to the longest possible prefix of s representing an integer in a given conversion base, the actual conversion base used, and the prefix length. The syntax of integers follows the syntax of signed integer literals in Go.

If the base argument is 0, the string prefix determines the actual conversion base. A prefix of “0x” or “0X” selects base 16; the “0” prefix selects base 8. Otherwise the selected base is 10.

func MakeInt 

func MakeInt(sign bool, mant Natural) *Integer

MakeInt makes an integer given a sign and a mantissa. The number is positive (>= 0) if sign is false or the mantissa is zero; it is negative otherwise.

func (*Integer) Abs 

func (x *Integer) Abs() Natural

Abs returns the absolute value of x.

func (*Integer) Add 

func (x *Integer) Add(y *Integer) *Integer

Add returns the sum x + y.

func (*Integer) And 

func (x *Integer) And(y *Integer) *Integer

And returns the “bitwise and” x & y for the 2's-complement representation of x and y.

func (*Integer) AndNot 

func (x *Integer) AndNot(y *Integer) *Integer

AndNot returns the “bitwise clear” x &^ y for the 2's-complement representation of x and y.

func (*Integer) Cmp 

func (x *Integer) Cmp(y *Integer) int

Cmp compares x and y. The result is an int value that is 

<  0 if x <  y
== 0 if x == y
>  0 if x >  y

func (*Integer) Div 

func (x *Integer) Div(y *Integer) *Integer

Div returns the quotient q = x / y for y != 0. If y == 0, a division-by-zero run-time error occurs.

Div and Mod implement Euclidian division and modulus: 

q = x.Div(y)
r = x.Mod(y) with: 0 <= r < |q| and: y = x*q + r

(Raymond T. Boute, “The Euclidian definition of the functions div and mod”. ACM Transactions on Programming Languages and Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992. ACM press.)

func (*Integer) DivMod 

func (x *Integer) DivMod(y *Integer) (*Integer, *Integer)

DivMod returns the pair (x.Div(y), x.Mod(y)).

func (*Integer) Format 

func (x *Integer) Format(h fmt.State, c int)

Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal).

func (*Integer) IsEven 

func (x *Integer) IsEven() bool

IsEven returns true iff x is divisible by 2.

func (*Integer) IsNeg 

func (x *Integer) IsNeg() bool

IsNeg returns true iff x < 0.

func (*Integer) IsOdd 

func (x *Integer) IsOdd() bool

IsOdd returns true iff x is not divisible by 2.

func (*Integer) IsPos 

func (x *Integer) IsPos() bool

IsPos returns true iff x >= 0.

func (*Integer) IsZero 

func (x *Integer) IsZero() bool

IsZero returns true iff x == 0.

func (*Integer) Mod 

func (x *Integer) Mod(y *Integer) *Integer

Mod returns the modulus r of the division x / y for y != 0, with r = x - y*x.Div(y). r is always positive. If y == 0, a division-by-zero run-time error occurs.

func (*Integer) Mul 

func (x *Integer) Mul(y *Integer) *Integer

Mul returns the product x * y.

func (*Integer) Mul1 

func (x *Integer) Mul1(d int64) *Integer

Mul1 returns the product x * d.

func (*Integer) MulNat 

func (x *Integer) MulNat(y Natural) *Integer

MulNat returns the product x * y, where y is a (unsigned) natural number.

func (*Integer) Neg 

func (x *Integer) Neg() *Integer

Neg returns the negated value of x.

func (*Integer) Not 

func (x *Integer) Not() *Integer

Not returns the “bitwise not” ^x for the 2's-complement representation of x.

func (*Integer) Or 

func (x *Integer) Or(y *Integer) *Integer

Or returns the “bitwise or” x | y for the 2's-complement representation of x and y.

func (*Integer) Quo 

func (x *Integer) Quo(y *Integer) *Integer

Quo returns the quotient q = x / y for y != 0. If y == 0, a division-by-zero run-time error occurs.

Quo and Rem implement T-division and modulus (like C99): 

q = x.Quo(y) = trunc(x/y)  (truncation towards zero)
r = x.Rem(y) = x - y*q

(Daan Leijen, “Division and Modulus for Computer Scientists”.)

func (*Integer) QuoRem 

func (x *Integer) QuoRem(y *Integer) (*Integer, *Integer)

QuoRem returns the pair (x.Quo(y), x.Rem(y)) for y != 0. If y == 0, a division-by-zero run-time error occurs.

func (*Integer) Rem 

func (x *Integer) Rem(y *Integer) *Integer

Rem returns the remainder r of the division x / y for y != 0, with r = x - y*x.Quo(y). Unless r is zero, its sign corresponds to the sign of x. If y == 0, a division-by-zero run-time error occurs.

func (*Integer) Shl 

func (x *Integer) Shl(s uint) *Integer

Shl implements “shift left” x << s. It returns x * 2^s.

func (*Integer) Shr 

func (x *Integer) Shr(s uint) *Integer

Shr implements “shift right” x >> s. It returns x / 2^s.

func (*Integer) String 

func (x *Integer) String() string

String converts x to its decimal string representation. x.String() is the same as x.ToString(10).

func (*Integer) Sub 

func (x *Integer) Sub(y *Integer) *Integer

Sub returns the difference x - y.

func (*Integer) ToString 

func (x *Integer) ToString(base uint) string

ToString converts x to a string for a given base, with 2 <= base <= 16.

func (*Integer) Value 

func (x *Integer) Value() int64

Value returns the value of x, if x fits into an int64; otherwise the result is undefined.

func (*Integer) Xor 

func (x *Integer) Xor(y *Integer) *Integer

Xor returns the “bitwise xor” x | y for the 2's-complement representation of x and y.

type Natural 

type Natural []digit

Natural represents an unsigned integer value of arbitrary precision.

func Binomial 

func Binomial(n, k uint) Natural

Binomial computes the binomial coefficient of (n, k).

func Fact 

func Fact(n uint) Natural

Fact computes the factorial of n (Fact(n) == MulRange(2, n)).

func MulRange 

func MulRange(a, b uint) Natural

MulRange computes the product of all the unsigned integers in the range [a, b] inclusively.

func Nat 

func Nat(x uint64) Natural

Nat creates a small natural number with value x.

func NatFromString 

func NatFromString(s string, base uint) (Natural, uint, int)

NatFromString returns the natural number corresponding to the longest possible prefix of s representing a natural number in a given conversion base, the actual conversion base used, and the prefix length. The syntax of natural numbers follows the syntax of unsigned integer literals in Go.

If the base argument is 0, the string prefix determines the actual conversion base. A prefix of “0x” or “0X” selects base 16; the “0” prefix selects base 8. Otherwise the selected base is 10.

func (Natural) Add 

func (x Natural) Add(y Natural) Natural

Add returns the sum z = x + y.

func (Natural) And 

func (x Natural) And(y Natural) Natural

And returns the “bitwise and” x & y for the 2's-complement representation of x and y.

func (Natural) AndNot 

func (x Natural) AndNot(y Natural) Natural

AndNot returns the “bitwise clear” x &^ y for the 2's-complement representation of x and y.

func (Natural) Cmp 

func (x Natural) Cmp(y Natural) int

Cmp compares x and y. The result is an int value 

<  0 if x <  y
== 0 if x == y
>  0 if x >  y

func (Natural) Div 

func (x Natural) Div(y Natural) Natural

Div returns the quotient q = x / y for y > 0, with x = y*q + r and 0 <= r < y. If y == 0, a division-by-zero run-time error occurs.

func (Natural) DivMod 

func (x Natural) DivMod(y Natural) (Natural, Natural)

DivMod returns the pair (x.Div(y), x.Mod(y)) for y > 0. If y == 0, a division-by-zero run-time error occurs.

func (Natural) Format 

func (x Natural) Format(h fmt.State, c int)

Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal).

func (Natural) Gcd 

func (x Natural) Gcd(y Natural) Natural

Gcd computes the gcd of x and y.

func (Natural) IsEven 

func (x Natural) IsEven() bool

IsEven returns true iff x is divisible by 2.

func (Natural) IsOdd 

func (x Natural) IsOdd() bool

IsOdd returns true iff x is not divisible by 2.

func (Natural) IsZero 

func (x Natural) IsZero() bool

IsZero returns true iff x == 0.

func (Natural) Log2 

func (x Natural) Log2() uint

Log2 computes the binary logarithm of x for x > 0. The result is the integer n for which 2^n <= x < 2^(n+1). If x == 0 a run-time error occurs.

func (Natural) Mod 

func (x Natural) Mod(y Natural) Natural

Mod returns the modulus r of the division x / y for y > 0, with x = y*q + r and 0 <= r < y. If y == 0, a division-by-zero run-time error occurs.

func (Natural) Mul 

func (x Natural) Mul(y Natural) Natural

Mul returns the product x * y.

func (Natural) Mul1 

func (x Natural) Mul1(d uint64) Natural

Mul1 returns the product x * d.

func (Natural) Or 

func (x Natural) Or(y Natural) Natural

Or returns the “bitwise or” x | y for the 2's-complement representation of x and y.

func (Natural) Pop 

func (x Natural) Pop() uint

Pop computes the “population count” of (the number of 1 bits in) x.

func (Natural) Pow 

func (xp Natural) Pow(n uint) Natural

Pow computes x to the power of n.

func (Natural) Shl 

func (x Natural) Shl(s uint) Natural

Shl implements “shift left” x << s. It returns x * 2^s.

func (Natural) Shr 

func (x Natural) Shr(s uint) Natural

Shr implements “shift right” x >> s. It returns x / 2^s.

func (Natural) String 

func (x Natural) String() string

String converts x to its decimal string representation. x.String() is the same as x.ToString(10).

func (Natural) Sub 

func (x Natural) Sub(y Natural) Natural

Sub returns the difference x - y for x >= y. If x < y, an underflow run-time error occurs (use Cmp to test if x >= y).

func (Natural) ToString 

func (x Natural) ToString(base uint) string

ToString converts x to a string for a given base, with 2 <= base <= 16.

func (Natural) Value 

func (x Natural) Value() uint64

Value returns the lowest 64bits of x.

func (Natural) Xor 

func (x Natural) Xor(y Natural) Natural

Xor returns the “bitwise exclusive or” x ^ y for the 2's-complement representation of x and y.

type Rational 

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

Rational represents a quotient a/b of arbitrary precision.

func MakeRat 

func MakeRat(a *Integer, b Natural) *Rational

MakeRat makes a rational number given a numerator a and a denominator b.

func Rat 

func Rat(a0 int64, b0 int64) *Rational

Rat creates a small rational number with value a0/b0.

func RatFromString 

func RatFromString(s string, base uint) (*Rational, uint, int)

RatFromString returns the rational number corresponding to the longest possible prefix of s representing a rational number in a given conversion base, the actual conversion base used, and the prefix length. The syntax of a rational number is: 

rational = mantissa [exponent] .
mantissa = integer ('/' natural | '.' natural) .
exponent = ('e'|'E') integer .

If the base argument is 0, the string prefix determines the actual conversion base for the mantissa. A prefix of “0x” or “0X” selects base 16; the “0” prefix selects base 8. Otherwise the selected base is 10. If the mantissa is represented via a division, both the numerator and denominator may have different base prefixes; in that case the base of of the numerator is returned. If the mantissa contains a decimal point, the base for the fractional part is the same as for the part before the decimal point and the fractional part does not accept a base prefix. The base for the exponent is always 10.

func (*Rational) Add 

func (x *Rational) Add(y *Rational) *Rational

Add returns the sum x + y.

func (*Rational) Cmp 

func (x *Rational) Cmp(y *Rational) int

Cmp compares x and y. The result is an int value 

<  0 if x <  y
== 0 if x == y
>  0 if x >  y

func (*Rational) Format 

func (x *Rational) Format(h fmt.State, c int)

Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal).

func (*Rational) IsInt 

func (x *Rational) IsInt() bool

IsInt returns true iff x can be written with a denominator 1 in the form x == x'/1; i.e., if x is an integer value.

func (*Rational) IsNeg 

func (x *Rational) IsNeg() bool

IsNeg returns true iff x < 0.

func (*Rational) IsPos 

func (x *Rational) IsPos() bool

IsPos returns true iff x > 0.

func (*Rational) IsZero 

func (x *Rational) IsZero() bool

IsZero returns true iff x == 0.

func (*Rational) Mul 

func (x *Rational) Mul(y *Rational) *Rational

Mul returns the product x * y.

func (*Rational) Neg 

func (x *Rational) Neg() *Rational

Neg returns the negated value of x.

func (*Rational) Quo 

func (x *Rational) Quo(y *Rational) *Rational

Quo returns the quotient x / y for y != 0. If y == 0, a division-by-zero run-time error occurs.

func (*Rational) String 

func (x *Rational) String() string

String converts x to its decimal string representation. x.String() is the same as x.ToString(10).

func (*Rational) Sub 

func (x *Rational) Sub(y *Rational) *Rational

Sub returns the difference x - y.

func (*Rational) ToString 

func (x *Rational) ToString(base uint) string

ToString converts x to a string for a given base, with 2 <= base <= 16. The string representation is of the form "n" if x is an integer; otherwise it is of form "n/d".

func (*Rational) Value 

func (x *Rational) Value() (numerator *Integer, denominator Natural)

Value returns the numerator and denominator of x.

Source Files

View all Source files

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.