src/pkg/bignum/integer.go

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Integer numbers
//
// Integers are normalized if the mantissa is normalized and the sign is
// false for mant == 0. Use MakeInt to create normalized Integers.

package bignum

import (
	"fmt"
)

// TODO(gri) Complete the set of in-place operations.

// Integer represents a signed integer value of arbitrary precision.
//
type Integer struct {
	sign bool
	mant Natural
}


// 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 MakeInt(sign bool, mant Natural) *Integer {
	if mant.IsZero() {
		sign = false // normalize
	}
	return &Integer{sign, mant}
}


// Int creates a small integer with value x.
//
func Int(x int64) *Integer {
	var ux uint64
	if x < 0 {
		// For the most negative x, -x == x, and
		// the bit pattern has the correct value.
		ux = uint64(-x)
	} else {
		ux = uint64(x)
	}
	return MakeInt(x < 0, Nat(ux))
}


// Value returns the value of x, if x fits into an int64;
// otherwise the result is undefined.
//
func (x *Integer) Value() int64 {
	z := int64(x.mant.Value())
	if x.sign {
		z = -z
	}
	return z
}


// Abs returns the absolute value of x.
//
func (x *Integer) Abs() Natural { return x.mant }


// Predicates

// IsEven returns true iff x is divisible by 2.
//
func (x *Integer) IsEven() bool { return x.mant.IsEven() }


// IsOdd returns true iff x is not divisible by 2.
//
func (x *Integer) IsOdd() bool { return x.mant.IsOdd() }


// IsZero returns true iff x == 0.
//
func (x *Integer) IsZero() bool { return x.mant.IsZero() }


// IsNeg returns true iff x < 0.
//
func (x *Integer) IsNeg() bool { return x.sign && !x.mant.IsZero() }


// IsPos returns true iff x >= 0.
//
func (x *Integer) IsPos() bool { return !x.sign && !x.mant.IsZero() }


// Operations

// Neg returns the negated value of x.
//
func (x *Integer) Neg() *Integer { return MakeInt(!x.sign, x.mant) }


// Iadd sets z to the sum x + y.
// z must exist and may be x or y.
//
func Iadd(z, x, y *Integer) {
	if x.sign == y.sign {
		// x + y == x + y
		// (-x) + (-y) == -(x + y)
		z.sign = x.sign
		Nadd(&z.mant, x.mant, y.mant)
	} else {
		// x + (-y) == x - y == -(y - x)
		// (-x) + y == y - x == -(x - y)
		if x.mant.Cmp(y.mant) >= 0 {
			z.sign = x.sign
			Nsub(&z.mant, x.mant, y.mant)
		} else {
			z.sign = !x.sign
			Nsub(&z.mant, y.mant, x.mant)
		}
	}
}


// Add returns the sum x + y.
//
func (x *Integer) Add(y *Integer) *Integer {
	var z Integer
	Iadd(&z, x, y)
	return &z
}


func Isub(z, x, y *Integer) {
	if x.sign != y.sign {
		// x - (-y) == x + y
		// (-x) - y == -(x + y)
		z.sign = x.sign
		Nadd(&z.mant, x.mant, y.mant)
	} else {
		// x - y == x - y == -(y - x)
		// (-x) - (-y) == y - x == -(x - y)
		if x.mant.Cmp(y.mant) >= 0 {
			z.sign = x.sign
			Nsub(&z.mant, x.mant, y.mant)
		} else {
			z.sign = !x.sign
			Nsub(&z.mant, y.mant, x.mant)
		}
	}
}


// Sub returns the difference x - y.
//
func (x *Integer) Sub(y *Integer) *Integer {
	var z Integer
	Isub(&z, x, y)
	return &z
}


// Nscale sets *z to the scaled value (*z) * d.
//
func Iscale(z *Integer, d int64) {
	f := uint64(d)
	if d < 0 {
		f = uint64(-d)
	}
	z.sign = z.sign != (d < 0)
	Nscale(&z.mant, f)
}


// Mul1 returns the product x * d.
//
func (x *Integer) Mul1(d int64) *Integer {
	f := uint64(d)
	if d < 0 {
		f = uint64(-d)
	}
	return MakeInt(x.sign != (d < 0), x.mant.Mul1(f))
}


// Mul returns the product x * y.
//
func (x *Integer) Mul(y *Integer) *Integer {
	// x * y == x * y
	// x * (-y) == -(x * y)
	// (-x) * y == -(x * y)
	// (-x) * (-y) == x * y
	return MakeInt(x.sign != y.sign, x.mant.Mul(y.mant))
}


// MulNat returns the product x * y, where y is a (unsigned) natural number.
//
func (x *Integer) MulNat(y Natural) *Integer {
	// x * y == x * y
	// (-x) * y == -(x * y)
	return MakeInt(x.sign, x.mant.Mul(y))
}


// 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 (x *Integer) Quo(y *Integer) *Integer {
	// x / y == x / y
	// x / (-y) == -(x / y)
	// (-x) / y == -(x / y)
	// (-x) / (-y) == x / y
	return MakeInt(x.sign != y.sign, x.mant.Div(y.mant))
}


// 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 (x *Integer) Rem(y *Integer) *Integer {
	// x % y == x % y
	// x % (-y) == x % y
	// (-x) % y == -(x % y)
	// (-x) % (-y) == -(x % y)
	return MakeInt(x.sign, x.mant.Mod(y.mant))
}


// 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 (x *Integer) QuoRem(y *Integer) (*Integer, *Integer) {
	q, r := x.mant.DivMod(y.mant)
	return MakeInt(x.sign != y.sign, q), MakeInt(x.sign, r)
}


// 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 (x *Integer) Div(y *Integer) *Integer {
	q, r := x.QuoRem(y)
	if r.IsNeg() {
		if y.IsPos() {
			q = q.Sub(Int(1))
		} else {
			q = q.Add(Int(1))
		}
	}
	return q
}


// 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 (x *Integer) Mod(y *Integer) *Integer {
	r := x.Rem(y)
	if r.IsNeg() {
		if y.IsPos() {
			r = r.Add(y)
		} else {
			r = r.Sub(y)
		}
	}
	return r
}


// DivMod returns the pair (x.Div(y), x.Mod(y)).
//
func (x *Integer) DivMod(y *Integer) (*Integer, *Integer) {
	q, r := x.QuoRem(y)
	if r.IsNeg() {
		if y.IsPos() {
			q = q.Sub(Int(1))
			r = r.Add(y)
		} else {
			q = q.Add(Int(1))
			r = r.Sub(y)
		}
	}
	return q, r
}


// Shl implements ``shift left'' x << s. It returns x * 2^s.
//
func (x *Integer) Shl(s uint) *Integer { return MakeInt(x.sign, x.mant.Shl(s)) }


// The bitwise operations on integers are defined on the 2's-complement
// representation of integers. From
//
//   -x == ^x + 1  (1)  2's complement representation
//
// follows:
//
//   -(x) == ^(x) + 1
//   -(-x) == ^(-x) + 1
//   x-1 == ^(-x)
//   ^(x-1) == -x  (2)
//
// Using (1) and (2), operations on negative integers of the form -x are
// converted to operations on negated positive integers of the form ~(x-1).


// Shr implements ``shift right'' x >> s. It returns x / 2^s.
//
func (x *Integer) Shr(s uint) *Integer {
	if x.sign {
		// (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
		return MakeInt(true, x.mant.Sub(Nat(1)).Shr(s).Add(Nat(1)))
	}

	return MakeInt(false, x.mant.Shr(s))
}


// Not returns the ``bitwise not'' ^x for the 2's-complement representation of x.
func (x *Integer) Not() *Integer {
	if x.sign {
		// ^(-x) == ^(^(x-1)) == x-1
		return MakeInt(false, x.mant.Sub(Nat(1)))
	}

	// ^x == -x-1 == -(x+1)
	return MakeInt(true, x.mant.Add(Nat(1)))
}


// And returns the ``bitwise and'' x & y for the 2's-complement representation of x and y.
//
func (x *Integer) And(y *Integer) *Integer {
	if x.sign == y.sign {
		if x.sign {
			// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
			return MakeInt(true, x.mant.Sub(Nat(1)).Or(y.mant.Sub(Nat(1))).Add(Nat(1)))
		}

		// x & y == x & y
		return MakeInt(false, x.mant.And(y.mant))
	}

	// x.sign != y.sign
	if x.sign {
		x, y = y, x // & is symmetric
	}

	// x & (-y) == x & ^(y-1) == x &^ (y-1)
	return MakeInt(false, x.mant.AndNot(y.mant.Sub(Nat(1))))
}


// AndNot returns the ``bitwise clear'' x &^ y for the 2's-complement representation of x and y.
//
func (x *Integer) AndNot(y *Integer) *Integer {
	if x.sign == y.sign {
		if x.sign {
			// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
			return MakeInt(false, y.mant.Sub(Nat(1)).AndNot(x.mant.Sub(Nat(1))))
		}

		// x &^ y == x &^ y
		return MakeInt(false, x.mant.AndNot(y.mant))
	}

	if x.sign {
		// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
		return MakeInt(true, x.mant.Sub(Nat(1)).Or(y.mant).Add(Nat(1)))
	}

	// x &^ (-y) == x &^ ^(y-1) == x & (y-1)
	return MakeInt(false, x.mant.And(y.mant.Sub(Nat(1))))
}


// Or returns the ``bitwise or'' x | y for the 2's-complement representation of x and y.
//
func (x *Integer) Or(y *Integer) *Integer {
	if x.sign == y.sign {
		if x.sign {
			// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
			return MakeInt(true, x.mant.Sub(Nat(1)).And(y.mant.Sub(Nat(1))).Add(Nat(1)))
		}

		// x | y == x | y
		return MakeInt(false, x.mant.Or(y.mant))
	}

	// x.sign != y.sign
	if x.sign {
		x, y = y, x // | or symmetric
	}

	// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
	return MakeInt(true, y.mant.Sub(Nat(1)).AndNot(x.mant).Add(Nat(1)))
}


// Xor returns the ``bitwise xor'' x | y for the 2's-complement representation of x and y.
//
func (x *Integer) Xor(y *Integer) *Integer {
	if x.sign == y.sign {
		if x.sign {
			// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
			return MakeInt(false, x.mant.Sub(Nat(1)).Xor(y.mant.Sub(Nat(1))))
		}

		// x ^ y == x ^ y
		return MakeInt(false, x.mant.Xor(y.mant))
	}

	// x.sign != y.sign
	if x.sign {
		x, y = y, x // ^ is symmetric
	}

	// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
	return MakeInt(true, x.mant.Xor(y.mant.Sub(Nat(1))).Add(Nat(1)))
}


// 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 (x *Integer) Cmp(y *Integer) int {
	// x cmp y == x cmp y
	// x cmp (-y) == x
	// (-x) cmp y == y
	// (-x) cmp (-y) == -(x cmp y)
	var r int
	switch {
	case x.sign == y.sign:
		r = x.mant.Cmp(y.mant)
		if x.sign {
			r = -r
		}
	case x.sign:
		r = -1
	case y.sign:
		r = 1
	}
	return r
}


// ToString converts x to a string for a given base, with 2 <= base <= 16.
//
func (x *Integer) ToString(base uint) string {
	if x.mant.IsZero() {
		return "0"
	}
	var s string
	if x.sign {
		s = "-"
	}
	return s + x.mant.ToString(base)
}


// String converts x to its decimal string representation.
// x.String() is the same as x.ToString(10).
//
func (x *Integer) String() string { return x.ToString(10) }


// Format is a support routine for fmt.Formatter. It accepts
// the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal).
//
func (x *Integer) Format(h fmt.State, c int) { fmt.Fprintf(h, "%s", x.ToString(fmtbase(c))) }


// 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 IntFromString(s string, base uint) (*Integer, uint, int) {
	// skip sign, if any
	i0 := 0
	if len(s) > 0 && (s[0] == '-' || s[0] == '+') {
		i0 = 1
	}

	mant, base, slen := NatFromString(s[i0:], base)

	return MakeInt(i0 > 0 && s[0] == '-', mant), base, i0 + slen
}