src/pkg/big/int.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.

// This file implements signed multi-precision integers.

package big

// An Int represents a signed multi-precision integer.
// The zero value for an Int represents the value 0.
type Int struct {
	neg	bool;	// sign
	abs	[]Word;	// absolute value of the integer
}


// New allocates and returns a new Int set to x.
func (z *Int) New(x int64) *Int {
	z.neg = false;
	if x < 0 {
		z.neg = true;
		x = -x;
	}
	z.abs = newN(z.abs, uint64(x));
	return z;
}


// NewInt allocates and returns a new Int set to x.
func NewInt(x int64) *Int	{ return new(Int).New(x) }


// Set sets z to x.
func (z *Int) Set(x *Int) *Int {
	z.neg = x.neg;
	z.abs = setN(z.abs, x.abs);
	return z;
}


// Add computes z = x+y.
func (z *Int) Add(x, y *Int) *Int {
	if x.neg == y.neg {
		// x + y == x + y
		// (-x) + (-y) == -(x + y)
		z.neg = x.neg;
		z.abs = addNN(z.abs, x.abs, y.abs);
	} else {
		// x + (-y) == x - y == -(y - x)
		// (-x) + y == y - x == -(x - y)
		if cmpNN(x.abs, y.abs) >= 0 {
			z.neg = x.neg;
			z.abs = subNN(z.abs, x.abs, y.abs);
		} else {
			z.neg = !x.neg;
			z.abs = subNN(z.abs, y.abs, x.abs);
		}
	}
	if len(z.abs) == 0 {
		z.neg = false	// 0 has no sign
	}
	return z;
}


// Sub computes z = x-y.
func (z *Int) Sub(x, y *Int) *Int {
	if x.neg != y.neg {
		// x - (-y) == x + y
		// (-x) - y == -(x + y)
		z.neg = x.neg;
		z.abs = addNN(z.abs, x.abs, y.abs);
	} else {
		// x - y == x - y == -(y - x)
		// (-x) - (-y) == y - x == -(x - y)
		if cmpNN(x.abs, y.abs) >= 0 {
			z.neg = x.neg;
			z.abs = subNN(z.abs, x.abs, y.abs);
		} else {
			z.neg = !x.neg;
			z.abs = subNN(z.abs, y.abs, x.abs);
		}
	}
	if len(z.abs) == 0 {
		z.neg = false	// 0 has no sign
	}
	return z;
}


// Mul computes z = x*y.
func (z *Int) Mul(x, y *Int) *Int {
	// x * y == x * y
	// x * (-y) == -(x * y)
	// (-x) * y == -(x * y)
	// (-x) * (-y) == x * y
	z.abs = mulNN(z.abs, x.abs, y.abs);
	z.neg = len(z.abs) > 0 && x.neg != y.neg;	// 0 has no sign
	return z;
}


// Div calculates q = (x-r)/y where 0 <= r < y. The receiver is set to q.
func (z *Int) Div(x, y *Int) (q, r *Int) {
	q = z;
	r = new(Int);
	div(q, r, x, y);
	return;
}


// Mod calculates q = (x-r)/y and returns r.
func (z *Int) Mod(x, y *Int) (r *Int) {
	q := new(Int);
	r = z;
	div(q, r, x, y);
	return;
}


func div(q, r, x, y *Int) {
	if len(y.abs) == 0 {
		panic("Divide by zero undefined")
	}

	if cmpNN(x.abs, y.abs) < 0 {
		q.neg = false;
		q.abs = nil;
		r.neg = y.neg;

		src := x.abs;
		dst := x.abs;
		if r == x {
			dst = nil
		}

		r.abs = makeN(dst, len(src), false);
		for i, v := range src {
			r.abs[i] = v
		}
		return;
	}

	if len(y.abs) == 1 {
		var rprime Word;
		q.abs, rprime = divNW(q.abs, x.abs, y.abs[0]);
		if rprime > 0 {
			r.abs = makeN(r.abs, 1, false);
			r.abs[0] = rprime;
			r.neg = x.neg;
		}
		q.neg = len(q.abs) > 0 && x.neg != y.neg;
		return;
	}

	q.neg = x.neg != y.neg;
	r.neg = x.neg;
	q.abs, r.abs = divNN(q.abs, r.abs, x.abs, y.abs);
	return;
}


// Neg computes z = -x.
func (z *Int) Neg(x *Int) *Int {
	z.abs = setN(z.abs, x.abs);
	z.neg = len(z.abs) > 0 && !x.neg;	// 0 has no sign
	return z;
}


// TODO(gri) Should this be x.Cmp(y) instead?

// CmpInt compares x and y. The result is
//
//   -1 if x <  y
//    0 if x == y
//   +1 if x >  y
//
func CmpInt(x, y *Int) (r int) {
	// x cmp y == x cmp y
	// x cmp (-y) == x
	// (-x) cmp y == y
	// (-x) cmp (-y) == -(x cmp y)
	switch {
	case x.neg == y.neg:
		r = cmpNN(x.abs, y.abs);
		if x.neg {
			r = -r
		}
	case x.neg:
		r = -1
	default:
		r = 1
	}
	return;
}


func (z *Int) String() string {
	s := "";
	if z.neg {
		s = "-"
	}
	return s + stringN(z.abs, 10);
}


// SetString sets z to the value of s, interpreted in the given base.
// If base is 0 then SetString attempts to detect the base by at the prefix of
// s. '0x' implies base 16, '0' implies base 8. Otherwise base 10 is assumed.
func (z *Int) SetString(s string, base int) (*Int, bool) {
	var scanned int;

	if base == 1 || base > 16 {
		goto Error
	}

	if len(s) == 0 {
		goto Error
	}

	if s[0] == '-' {
		z.neg = true;
		s = s[1:len(s)];
	} else {
		z.neg = false
	}

	z.abs, _, scanned = scanN(z.abs, s, base);
	if scanned != len(s) {
		goto Error
	}

	return z, true;

Error:
	z.neg = false;
	z.abs = nil;
	return nil, false;
}


// SetBytes interprets b as the bytes of a big-endian, unsigned integer and
// sets x to that value.
func (z *Int) SetBytes(b []byte) *Int {
	s := int(_S);
	z.abs = makeN(z.abs, (len(b)+s-1)/s, false);
	z.neg = false;

	j := 0;
	for len(b) >= s {
		var w Word;

		for i := s; i > 0; i-- {
			w <<= 8;
			w |= Word(b[len(b)-i]);
		}

		z.abs[j] = w;
		j++;
		b = b[0 : len(b)-s];
	}

	if len(b) > 0 {
		var w Word;

		for i := len(b); i > 0; i-- {
			w <<= 8;
			w |= Word(b[len(b)-i]);
		}

		z.abs[j] = w;
	}

	z.abs = normN(z.abs);

	return z;
}


// Bytes returns the absolute value of x as a big-endian byte array.
func (z *Int) Bytes() []byte {
	s := int(_S);
	b := make([]byte, len(z.abs)*s);

	for i, w := range z.abs {
		wordBytes := b[(len(z.abs)-i-1)*s : (len(z.abs)-i)*s];
		for j := s - 1; j >= 0; j-- {
			wordBytes[j] = byte(w);
			w >>= 8;
		}
	}

	i := 0;
	for i < len(b) && b[i] == 0 {
		i++
	}

	return b[i:len(b)];
}


// Len returns the length of the absolute value of x in bits. Zero is
// considered to have a length of one.
func (z *Int) Len() int {
	if len(z.abs) == 0 {
		return 0
	}

	return len(z.abs)*int(_W) - int(leadingZeros(z.abs[len(z.abs)-1]));
}


// Exp sets z = x**y mod m. If m is nil, z = x**y.
// See Knuth, volume 2, section 4.6.3.
func (z *Int) Exp(x, y, m *Int) *Int {
	if y.neg || len(y.abs) == 0 {
		z.New(1);
		z.neg = x.neg;
		return z;
	}

	z.Set(x);
	v := y.abs[len(y.abs)-1];
	// It's invalid for the most significant word to be zero, therefore we
	// will find a one bit.
	shift := leadingZeros(v) + 1;
	v <<= shift;

	const mask = 1 << (_W - 1);

	// We walk through the bits of the exponent one by one. Each time we see
	// a bit, we square, thus doubling the power. If the bit is a one, we
	// also multiply by x, thus adding one to the power.

	w := int(_W) - int(shift);
	for j := 0; j < w; j++ {
		z.Mul(z, z);

		if v&mask != 0 {
			z.Mul(z, x)
		}

		if m != nil {
			z.Mod(z, m)
		}

		v <<= 1;
	}

	for i := len(y.abs) - 2; i >= 0; i-- {
		v = y.abs[i];

		for j := 0; j < int(_W); j++ {
			z.Mul(z, z);

			if v&mask != 0 {
				z.Mul(z, x)
			}

			if m != nil {
				z.Mod(z, m)
			}

			v <<= 1;
		}
	}

	z.neg = x.neg && y.abs[0]&1 == 1;
	return z;
}


// GcdInt sets d to the greatest common divisor of a and b, which must be
// positive numbers.
// If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y.
// If either a or b is not positive, GcdInt sets d = x = y = 0.
func GcdInt(d, x, y, a, b *Int) {
	if a.neg || b.neg {
		d.New(0);
		if x != nil {
			x.New(0)
		}
		if y != nil {
			y.New(0)
		}
		return;
	}

	A := new(Int).Set(a);
	B := new(Int).Set(b);

	X := new(Int);
	Y := new(Int).New(1);

	lastX := new(Int).New(1);
	lastY := new(Int);

	q := new(Int);
	temp := new(Int);

	for len(B.abs) > 0 {
		q, r := q.Div(A, B);

		A, B = B, r;

		temp.Set(X);
		X.Mul(X, q);
		X.neg = !X.neg;
		X.Add(X, lastX);
		lastX.Set(temp);

		temp.Set(Y);
		Y.Mul(Y, q);
		Y.neg = !Y.neg;
		Y.Add(Y, lastY);
		lastY.Set(temp);
	}

	if x != nil {
		*x = *lastX
	}

	if y != nil {
		*y = *lastY
	}

	*d = *A;
}