src/pkg/big/nat.go - go - Git at Google

 // 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 contains operations on unsigned multi-precision integers.
 // These are the building blocks for the operations on signed integers
 // and rationals.

 //	NOTE: PACKAGE UNDER CONSTRUCTION.
 //
 // The big package implements multi-precision arithmetic (big numbers).
 // The following numeric types are supported:
 //
 //	- Int	signed integers
 //
 // All methods on Int take the result as the receiver; if it is one
 // of the operands it may be overwritten (and its memory reused).
 // To enable chaining of operations, the result is also returned.
 //
 package big

 // An unsigned integer x of the form
 //
 //   x = x[n-1]*_B^(n-1) + x[n-2]*_B^(n-2) + ... + x[1]*_B + x[0]
 //
 // with 0 <= x[i] < _B and 0 <= i < n is stored in a slice of length n,
 // with the digits x[i] as the slice elements.
 //
 // A number is normalized if the slice contains no leading 0 digits.
 // During arithmetic operations, denormalized values may occur but are
 // always normalized before returning the final result. The normalized
 // representation of 0 is the empty or nil slice (length = 0).

 // TODO(gri) - convert these routines into methods for type 'nat'
 //           - decide if type 'nat' should be exported

 func normN(z []Word) []Word {
 	i := len(z);
 	for i > 0 && z[i-1] == 0 {
 		i--
 	}
 	z = z[0:i];
 	return z;
 }


 func makeN(z []Word, m int, clear bool) []Word {
 	if len(z) > m {
 		z = z[0:m];	// reuse z - has at least one extra word for a carry, if any
 		if clear {
 			for i := range z {
 				z[i] = 0
 			}
 		}
 		return z;
 	}

 	c := 4;	// minimum capacity
 	if m > c {
 		c = m
 	}
 	return make([]Word, m, c+1);	// +1: extra word for a carry, if any
 }


 func newN(z []Word, x uint64) []Word {
 	if x == 0 {
 		return makeN(z, 0, false)
 	}

 	// single-digit values
 	if x == uint64(Word(x)) {
 		z = makeN(z, 1, false);
 		z[0] = Word(x);
 		return z;
 	}

 	// compute number of words n required to represent x
 	n := 0;
 	for t := x; t > 0; t >>= _W {
 		n++
 	}

 	// split x into n words
 	z = makeN(z, n, false);
 	for i := 0; i < n; i++ {
 		z[i] = Word(x & _M);
 		x >>= _W;
 	}

 	return z;
 }


 func setN(z, x []Word) []Word {
 	z = makeN(z, len(x), false);
 	for i, d := range x {
 		z[i] = d
 	}
 	return z;
 }


 func addNN(z, x, y []Word) []Word {
 	m := len(x);
 	n := len(y);

 	switch {
 	case m < n:
 		return addNN(z, y, x)
 	case m == 0:
 		// n == 0 because m >= n; result is 0
 		return makeN(z, 0, false)
 	case n == 0:
 		// result is x
 		return setN(z, x)
 	}
 	// m > 0

 	z = makeN(z, m, false);
 	c := addVV(&z[0], &x[0], &y[0], n);
 	if m > n {
 		c = addVW(&z[n], &x[n], c, m-n)
 	}
 	if c > 0 {
 		z = z[0 : m+1];
 		z[m] = c;
 	}

 	return z;
 }


 func subNN(z, x, y []Word) []Word {
 	m := len(x);
 	n := len(y);

 	switch {
 	case m < n:
 		panic("underflow")
 	case m == 0:
 		// n == 0 because m >= n; result is 0
 		return makeN(z, 0, false)
 	case n == 0:
 		// result is x
 		return setN(z, x)
 	}
 	// m > 0

 	z = makeN(z, m, false);
 	c := subVV(&z[0], &x[0], &y[0], n);
 	if m > n {
 		c = subVW(&z[n], &x[n], c, m-n)
 	}
 	if c != 0 {
 		panic("underflow")
 	}
 	z = normN(z);

 	return z;
 }


 func cmpNN(x, y []Word) (r int) {
 	m := len(x);
 	n := len(y);
 	if m != n || m == 0 {
 		switch {
 		case m < n:
 			r = -1
 		case m > n:
 			r = 1
 		}
 		return;
 	}

 	i := m - 1;
 	for i > 0 && x[i] == y[i] {
 		i--
 	}

 	switch {
 	case x[i] < y[i]:
 		r = -1
 	case x[i] > y[i]:
 		r = 1
 	}
 	return;
 }


 func mulAddNWW(z, x []Word, y, r Word) []Word {
 	m := len(x);
 	if m == 0 || y == 0 {
 		return newN(z, uint64(r))	// result is r
 	}
 	// m > 0

 	z = makeN(z, m, false);
 	c := mulAddVWW(&z[0], &x[0], y, r, m);
 	if c > 0 {
 		z = z[0 : m+1];
 		z[m] = c;
 	}

 	return z;
 }


 func mulNN(z, x, y []Word) []Word {
 	m := len(x);
 	n := len(y);

 	switch {
 	case m < n:
 		return mulNN(z, y, x)
 	case m == 0 || n == 0:
 		return makeN(z, 0, false)
 	case n == 1:
 		return mulAddNWW(z, x, y[0], 0)
 	}
 	// m >= n && m > 1 && n > 1

 	z = makeN(z, m+n, true);
 	if &z[0] == &x[0] || &z[0] == &y[0] {
 		z = makeN(nil, m+n, true)	// z is an alias for x or y - cannot reuse
 	}
 	for i := 0; i < n; i++ {
 		if f := y[i]; f != 0 {
 			z[m+i] = addMulVVW(&z[i], &x[0], f, m)
 		}
 	}
 	z = normN(z);

 	return z;
 }


 // q = (x-r)/y, with 0 <= r < y
 func divNW(z, x []Word, y Word) (q []Word, r Word) {
 	m := len(x);
 	switch {
 	case y == 0:
 		panic("division by zero")
 	case y == 1:
 		q = setN(z, x);	// result is x
 		return;
 	case m == 0:
 		q = setN(z, nil);	// result is 0
 		return;
 	}
 	// m > 0
 	z = makeN(z, m, false);
 	r = divWVW(&z[0], 0, &x[0], y, m);
 	q = normN(z);
 	return;
 }


 // q = (uIn-r)/v, with 0 <= r < y
 // See Knuth, Volume 2, section 4.3.1, Algorithm D.
 // Preconditions:
 //    len(v) >= 2
 //    len(uIn) >= 1 + len(vIn)
 func divNN(z, z2, uIn, v []Word) (q, r []Word) {
 	n := len(v);
 	m := len(uIn) - len(v);

 	u := makeN(z2, len(uIn)+1, false);
 	qhatv := make([]Word, len(v)+1);
 	q = makeN(z, m+1, false);

 	// D1.
 	shift := leadingZeroBits(v[n-1]);
 	shiftLeft(v, v, shift);
 	shiftLeft(u, uIn, shift);
 	u[len(uIn)] = uIn[len(uIn)-1] >> (uint(_W) - uint(shift));

 	// D2.
 	for j := m; j >= 0; j-- {
 		// D3.
 		qhat, rhat := divWW_g(u[j+n], u[j+n-1], v[n-1]);

 		// x1 | x2 = q̂v_{n-2}
 		x1, x2 := mulWW_g(qhat, v[n-2]);
 		// test if q̂v_{n-2} > br̂ + u_{j+n-2}
 		for greaterThan(x1, x2, rhat, u[j+n-2]) {
 			qhat--;
 			prevRhat := rhat;
 			rhat += v[n-1];
 			// v[n-1] >= 0, so this tests for overflow.
 			if rhat < prevRhat {
 				break
 			}
 			x1, x2 = mulWW_g(qhat, v[n-2]);
 		}

 		// D4.
 		qhatv[len(v)] = mulAddVWW(&qhatv[0], &v[0], qhat, 0, len(v));

 		c := subVV(&u[j], &u[j], &qhatv[0], len(qhatv));
 		if c != 0 {
 			c := addVV(&u[j], &u[j], &v[0], len(v));
 			u[j+len(v)] += c;
 			qhat--;
 		}

 		q[j] = qhat;
 	}

 	q = normN(q);
 	shiftRight(u, u, shift);
 	shiftRight(v, v, shift);
 	r = normN(u);

 	return q, r;
 }


 // log2 computes the integer binary logarithm of x.
 // The result is the integer n for which 2^n <= x < 2^(n+1).
 // If x == 0, the result is -1.
 func log2(x Word) int {
 	n := 0;
 	for ; x > 0; x >>= 1 {
 		n++
 	}
 	return n - 1;
 }


 // log2N computes the integer binary logarithm of x.
 // The result is the integer n for which 2^n <= x < 2^(n+1).
 // If x == 0, the result is -1.
 func log2N(x []Word) int {
 	m := len(x);
 	if m > 0 {
 		return (m-1)*int(_W) + log2(x[m-1])
 	}
 	return -1;
 }


 func hexValue(ch byte) int {
 	var d byte;
 	switch {
 	case '0' <= ch && ch <= '9':
 		d = ch - '0'
 	case 'a' <= ch && ch <= 'f':
 		d = ch - 'a' + 10
 	case 'A' <= ch && ch <= 'F':
 		d = ch - 'A' + 10
 	default:
 		return -1
 	}
 	return int(d);
 }


 // scanN 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 scanN(z []Word, s string, base int) ([]Word, int, int) {
 	// determine base if necessary
 	i, n := 0, len(s);
 	if base == 0 {
 		base = 10;
 		if n > 0 && s[0] == '0' {
 			if n > 1 && (s[1] == 'x' || s[1] == 'X') {
 				if n == 2 {
 					// Reject a string which is just '0x' as nonsense.
 					return nil, 0, 0
 				}
 				base, i = 16, 2;
 			} else {
 				base, i = 8, 1
 			}
 		}
 	}
 	if base < 2 || 16 < base {
 		panic("illegal base")
 	}

 	// convert string
 	z = makeN(z, len(z), false);
 	for ; i < n; i++ {
 		d := hexValue(s[i]);
 		if 0 <= d && d < base {
 			z = mulAddNWW(z, z, Word(base), Word(d))
 		} else {
 			break
 		}
 	}

 	return z, base, i;
 }


 // string converts x to a string for a given base, with 2 <= base <= 16.
 // TODO(gri) in the style of the other routines, perhaps this should take
 //           a []byte buffer and return it
 func stringN(x []Word, base int) string {
 	if base < 2 || 16 < base {
 		panic("illegal base")
 	}

 	if len(x) == 0 {
 		return "0"
 	}

 	// allocate buffer for conversion
 	i := (log2N(x)+1)/log2(Word(base)) + 1;	// +1: round up
 	s := make([]byte, i);

 	// don't destroy x
 	q := setN(nil, x);

 	// convert
 	for len(q) > 0 {
 		i--;
 		var r Word;
 		q, r = divNW(q, q, Word(base));
 		s[i] = "0123456789abcdef"[r];
 	}

 	return string(s[i:len(s)]);
 }


 // leadingZeroBits returns the number of leading zero bits in x.
 func leadingZeroBits(x Word) int {
 	c := 0;
 	if x < 1<<(_W/2) {
 		x <<= _W / 2;
 		c = int(_W / 2);
 	}

 	for i := 0; x != 0; i++ {
 		if x&(1<<(_W-1)) != 0 {
 			return i + c
 		}
 		x <<= 1;
 	}

 	return int(_W);
 }


 func shiftLeft(dst, src []Word, n int) {
 	if len(src) == 0 {
 		return
 	}

 	ñ := uint(_W) - uint(n);
 	for i := len(src) - 1; i >= 1; i-- {
 		dst[i] = src[i] << uint(n);
 		dst[i] |= src[i-1] >> ñ;
 	}
 	dst[0] = src[0] << uint(n);
 }


 func shiftRight(dst, src []Word, n int) {
 	if len(src) == 0 {
 		return
 	}

 	ñ := uint(_W) - uint(n);
 	for i := 0; i < len(src)-1; i++ {
 		dst[i] = src[i] >> uint(n);
 		dst[i] |= src[i+1] << ñ;
 	}
 	dst[len(src)-1] = src[len(src)-1] >> uint(n);
 }


 // greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2)
 func greaterThan(x1, x2, y1, y2 Word) bool	{ return x1 > y1 || x1 == y1 && x2 > y2 }
	// 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 contains operations on unsigned multi-precision integers.
	// These are the building blocks for the operations on signed integers
	// and rationals.

	// NOTE: PACKAGE UNDER CONSTRUCTION.
	//
	// The big package implements multi-precision arithmetic (big numbers).
	// The following numeric types are supported:
	//
	// - Int signed integers
	//
	// All methods on Int take the result as the receiver; if it is one
	// of the operands it may be overwritten (and its memory reused).
	// To enable chaining of operations, the result is also returned.
	//
	package big

	// An unsigned integer x of the form
	//
	// x = x[n-1]_B^(n-1) + x[n-2]_B^(n-2) + ... + x[1]*_B + x[0]
	//
	// with 0 <= x[i] < _B and 0 <= i < n is stored in a slice of length n,
	// with the digits x[i] as the slice elements.
	//
	// A number is normalized if the slice contains no leading 0 digits.
	// During arithmetic operations, denormalized values may occur but are
	// always normalized before returning the final result. The normalized
	// representation of 0 is the empty or nil slice (length = 0).

	// TODO(gri) - convert these routines into methods for type 'nat'
	// - decide if type 'nat' should be exported

	func normN(z []Word) []Word {
	i := len(z);
	for i > 0 && z[i-1] == 0 {
	i--
	}
	z = z[0:i];
	return z;
	}


	func makeN(z []Word, m int, clear bool) []Word {
	if len(z) > m {
	z = z[0:m]; // reuse z - has at least one extra word for a carry, if any
	if clear {
	for i := range z {
	z[i] = 0
	}
	}
	return z;
	}

	c := 4; // minimum capacity
	if m > c {
	c = m
	}
	return make([]Word, m, c+1); // +1: extra word for a carry, if any
	}


	func newN(z []Word, x uint64) []Word {
	if x == 0 {
	return makeN(z, 0, false)
	}

	// single-digit values
	if x == uint64(Word(x)) {
	z = makeN(z, 1, false);
	z[0] = Word(x);
	return z;
	}

	// compute number of words n required to represent x
	n := 0;
	for t := x; t > 0; t >>= _W {
	n++
	}

	// split x into n words
	z = makeN(z, n, false);
	for i := 0; i < n; i++ {
	z[i] = Word(x & _M);
	x >>= _W;
	}

	return z;
	}


	func setN(z, x []Word) []Word {
	z = makeN(z, len(x), false);
	for i, d := range x {
	z[i] = d
	}
	return z;
	}


	func addNN(z, x, y []Word) []Word {
	m := len(x);
	n := len(y);

	switch {
	case m < n:
	return addNN(z, y, x)
	case m == 0:
	// n == 0 because m >= n; result is 0
	return makeN(z, 0, false)
	case n == 0:
	// result is x
	return setN(z, x)
	}
	// m > 0

	z = makeN(z, m, false);
	c := addVV(&z[0], &x[0], &y[0], n);
	if m > n {
	c = addVW(&z[n], &x[n], c, m-n)
	}
	if c > 0 {
	z = z[0 : m+1];
	z[m] = c;
	}

	return z;
	}


	func subNN(z, x, y []Word) []Word {
	m := len(x);
	n := len(y);

	switch {
	case m < n:
	panic("underflow")
	case m == 0:
	// n == 0 because m >= n; result is 0
	return makeN(z, 0, false)
	case n == 0:
	// result is x
	return setN(z, x)
	}
	// m > 0

	z = makeN(z, m, false);
	c := subVV(&z[0], &x[0], &y[0], n);
	if m > n {
	c = subVW(&z[n], &x[n], c, m-n)
	}
	if c != 0 {
	panic("underflow")
	}
	z = normN(z);

	return z;
	}


	func cmpNN(x, y []Word) (r int) {
	m := len(x);
	n := len(y);
	if m != n \|\| m == 0 {
	switch {
	case m < n:
	r = -1
	case m > n:
	r = 1
	}
	return;
	}

	i := m - 1;
	for i > 0 && x[i] == y[i] {
	i--
	}

	switch {
	case x[i] < y[i]:
	r = -1
	case x[i] > y[i]:
	r = 1
	}
	return;
	}


	func mulAddNWW(z, x []Word, y, r Word) []Word {
	m := len(x);
	if m == 0 \|\| y == 0 {
	return newN(z, uint64(r)) // result is r
	}
	// m > 0

	z = makeN(z, m, false);
	c := mulAddVWW(&z[0], &x[0], y, r, m);
	if c > 0 {
	z = z[0 : m+1];
	z[m] = c;
	}

	return z;
	}


	func mulNN(z, x, y []Word) []Word {
	m := len(x);
	n := len(y);

	switch {
	case m < n:
	return mulNN(z, y, x)
	case m == 0 \|\| n == 0:
	return makeN(z, 0, false)
	case n == 1:
	return mulAddNWW(z, x, y[0], 0)
	}
	// m >= n && m > 1 && n > 1

	z = makeN(z, m+n, true);
	if &z[0] == &x[0] \|\| &z[0] == &y[0] {
	z = makeN(nil, m+n, true) // z is an alias for x or y - cannot reuse
	}
	for i := 0; i < n; i++ {
	if f := y[i]; f != 0 {
	z[m+i] = addMulVVW(&z[i], &x[0], f, m)
	}
	}
	z = normN(z);

	return z;
	}


	// q = (x-r)/y, with 0 <= r < y
	func divNW(z, x []Word, y Word) (q []Word, r Word) {
	m := len(x);
	switch {
	case y == 0:
	panic("division by zero")
	case y == 1:
	q = setN(z, x); // result is x
	return;
	case m == 0:
	q = setN(z, nil); // result is 0
	return;
	}
	// m > 0
	z = makeN(z, m, false);
	r = divWVW(&z[0], 0, &x[0], y, m);
	q = normN(z);
	return;
	}


	// q = (uIn-r)/v, with 0 <= r < y
	// See Knuth, Volume 2, section 4.3.1, Algorithm D.
	// Preconditions:
	// len(v) >= 2
	// len(uIn) >= 1 + len(vIn)
	func divNN(z, z2, uIn, v []Word) (q, r []Word) {
	n := len(v);
	m := len(uIn) - len(v);

	u := makeN(z2, len(uIn)+1, false);
	qhatv := make([]Word, len(v)+1);
	q = makeN(z, m+1, false);

	// D1.
	shift := leadingZeroBits(v[n-1]);
	shiftLeft(v, v, shift);
	shiftLeft(u, uIn, shift);
	u[len(uIn)] = uIn[len(uIn)-1] >> (uint(_W) - uint(shift));

	// D2.
	for j := m; j >= 0; j-- {
	// D3.
	qhat, rhat := divWW_g(u[j+n], u[j+n-1], v[n-1]);

	// x1 \| x2 = q̂v_{n-2}
	x1, x2 := mulWW_g(qhat, v[n-2]);
	// test if q̂v_{n-2} > br̂ + u_{j+n-2}
	for greaterThan(x1, x2, rhat, u[j+n-2]) {
	qhat--;
	prevRhat := rhat;
	rhat += v[n-1];
	// v[n-1] >= 0, so this tests for overflow.
	if rhat < prevRhat {
	break
	}
	x1, x2 = mulWW_g(qhat, v[n-2]);
	}

	// D4.
	qhatv[len(v)] = mulAddVWW(&qhatv[0], &v[0], qhat, 0, len(v));

	c := subVV(&u[j], &u[j], &qhatv[0], len(qhatv));
	if c != 0 {
	c := addVV(&u[j], &u[j], &v[0], len(v));
	u[j+len(v)] += c;
	qhat--;
	}

	q[j] = qhat;
	}

	q = normN(q);
	shiftRight(u, u, shift);
	shiftRight(v, v, shift);
	r = normN(u);

	return q, r;
	}


	// log2 computes the integer binary logarithm of x.
	// The result is the integer n for which 2^n <= x < 2^(n+1).
	// If x == 0, the result is -1.
	func log2(x Word) int {
	n := 0;
	for ; x > 0; x >>= 1 {
	n++
	}
	return n - 1;
	}


	// log2N computes the integer binary logarithm of x.
	// The result is the integer n for which 2^n <= x < 2^(n+1).
	// If x == 0, the result is -1.
	func log2N(x []Word) int {
	m := len(x);
	if m > 0 {
	return (m-1)*int(_W) + log2(x[m-1])
	}
	return -1;
	}


	func hexValue(ch byte) int {
	var d byte;
	switch {
	case '0' <= ch && ch <= '9':
	d = ch - '0'
	case 'a' <= ch && ch <= 'f':
	d = ch - 'a' + 10
	case 'A' <= ch && ch <= 'F':
	d = ch - 'A' + 10
	default:
	return -1
	}
	return int(d);
	}


	// scanN 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 scanN(z []Word, s string, base int) ([]Word, int, int) {
	// determine base if necessary
	i, n := 0, len(s);
	if base == 0 {
	base = 10;
	if n > 0 && s[0] == '0' {
	if n > 1 && (s[1] == 'x' \|\| s[1] == 'X') {
	if n == 2 {
	// Reject a string which is just '0x' as nonsense.
	return nil, 0, 0
	}
	base, i = 16, 2;
	} else {
	base, i = 8, 1
	}
	}
	}
	if base < 2 \|\| 16 < base {
	panic("illegal base")
	}

	// convert string
	z = makeN(z, len(z), false);
	for ; i < n; i++ {
	d := hexValue(s[i]);
	if 0 <= d && d < base {
	z = mulAddNWW(z, z, Word(base), Word(d))
	} else {
	break
	}
	}

	return z, base, i;
	}


	// string converts x to a string for a given base, with 2 <= base <= 16.
	// TODO(gri) in the style of the other routines, perhaps this should take
	// a []byte buffer and return it
	func stringN(x []Word, base int) string {
	if base < 2 \|\| 16 < base {
	panic("illegal base")
	}

	if len(x) == 0 {
	return "0"
	}

	// allocate buffer for conversion
	i := (log2N(x)+1)/log2(Word(base)) + 1; // +1: round up
	s := make([]byte, i);

	// don't destroy x
	q := setN(nil, x);

	// convert
	for len(q) > 0 {
	i--;
	var r Word;
	q, r = divNW(q, q, Word(base));
	s[i] = "0123456789abcdef"[r];
	}

	return string(s[i:len(s)]);
	}


	// leadingZeroBits returns the number of leading zero bits in x.
	func leadingZeroBits(x Word) int {
	c := 0;
	if x < 1<<(_W/2) {
	x <<= _W / 2;
	c = int(_W / 2);
	}

	for i := 0; x != 0; i++ {
	if x&(1<<(_W-1)) != 0 {
	return i + c
	}
	x <<= 1;
	}

	return int(_W);
	}


	func shiftLeft(dst, src []Word, n int) {
	if len(src) == 0 {
	return
	}

	ñ := uint(_W) - uint(n);
	for i := len(src) - 1; i >= 1; i-- {
	dst[i] = src[i] << uint(n);
	dst[i] \|= src[i-1] >> ñ;
	}
	dst[0] = src[0] << uint(n);
	}


	func shiftRight(dst, src []Word, n int) {
	if len(src) == 0 {
	return
	}

	ñ := uint(_W) - uint(n);
	for i := 0; i < len(src)-1; i++ {
	dst[i] = src[i] >> uint(n);
	dst[i] \|= src[i+1] << ñ;
	}
	dst[len(src)-1] = src[len(src)-1] >> uint(n);
	}


	// greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2)
	func greaterThan(x1, x2, y1, y2 Word) bool { return x1 > y1 \|\| x1 == y1 && x2 > y2 }