The Go Programming Language

Source file src/pkg/big/int_test.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package big
     6	
     7	import (
     8		"bytes"
     9		"encoding/hex"
    10		"fmt"
    11		"gob"
    12		"testing"
    13		"testing/quick"
    14	)
    15	
    16	func isNormalized(x *Int) bool {
    17		if len(x.abs) == 0 {
    18			return !x.neg
    19		}
    20		// len(x.abs) > 0
    21		return x.abs[len(x.abs)-1] != 0
    22	}
    23	
    24	type funZZ func(z, x, y *Int) *Int
    25	type argZZ struct {
    26		z, x, y *Int
    27	}
    28	
    29	var sumZZ = []argZZ{
    30		{NewInt(0), NewInt(0), NewInt(0)},
    31		{NewInt(1), NewInt(1), NewInt(0)},
    32		{NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
    33		{NewInt(-1), NewInt(-1), NewInt(0)},
    34		{NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
    35		{NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
    36	}
    37	
    38	var prodZZ = []argZZ{
    39		{NewInt(0), NewInt(0), NewInt(0)},
    40		{NewInt(0), NewInt(1), NewInt(0)},
    41		{NewInt(1), NewInt(1), NewInt(1)},
    42		{NewInt(-991 * 991), NewInt(991), NewInt(-991)},
    43		// TODO(gri) add larger products
    44	}
    45	
    46	func TestSignZ(t *testing.T) {
    47		var zero Int
    48		for _, a := range sumZZ {
    49			s := a.z.Sign()
    50			e := a.z.Cmp(&zero)
    51			if s != e {
    52				t.Errorf("got %d; want %d for z = %v", s, e, a.z)
    53			}
    54		}
    55	}
    56	
    57	func TestSetZ(t *testing.T) {
    58		for _, a := range sumZZ {
    59			var z Int
    60			z.Set(a.z)
    61			if !isNormalized(&z) {
    62				t.Errorf("%v is not normalized", z)
    63			}
    64			if (&z).Cmp(a.z) != 0 {
    65				t.Errorf("got z = %v; want %v", z, a.z)
    66			}
    67		}
    68	}
    69	
    70	func TestAbsZ(t *testing.T) {
    71		var zero Int
    72		for _, a := range sumZZ {
    73			var z Int
    74			z.Abs(a.z)
    75			var e Int
    76			e.Set(a.z)
    77			if e.Cmp(&zero) < 0 {
    78				e.Sub(&zero, &e)
    79			}
    80			if z.Cmp(&e) != 0 {
    81				t.Errorf("got z = %v; want %v", z, e)
    82			}
    83		}
    84	}
    85	
    86	func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
    87		var z Int
    88		f(&z, a.x, a.y)
    89		if !isNormalized(&z) {
    90			t.Errorf("%s%v is not normalized", z, msg)
    91		}
    92		if (&z).Cmp(a.z) != 0 {
    93			t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
    94		}
    95	}
    96	
    97	func TestSumZZ(t *testing.T) {
    98		AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
    99		SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
   100		for _, a := range sumZZ {
   101			arg := a
   102			testFunZZ(t, "AddZZ", AddZZ, arg)
   103	
   104			arg = argZZ{a.z, a.y, a.x}
   105			testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
   106	
   107			arg = argZZ{a.x, a.z, a.y}
   108			testFunZZ(t, "SubZZ", SubZZ, arg)
   109	
   110			arg = argZZ{a.y, a.z, a.x}
   111			testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
   112		}
   113	}
   114	
   115	func TestProdZZ(t *testing.T) {
   116		MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
   117		for _, a := range prodZZ {
   118			arg := a
   119			testFunZZ(t, "MulZZ", MulZZ, arg)
   120	
   121			arg = argZZ{a.z, a.y, a.x}
   122			testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
   123		}
   124	}
   125	
   126	// mulBytes returns x*y via grade school multiplication. Both inputs
   127	// and the result are assumed to be in big-endian representation (to
   128	// match the semantics of Int.Bytes and Int.SetBytes).
   129	func mulBytes(x, y []byte) []byte {
   130		z := make([]byte, len(x)+len(y))
   131	
   132		// multiply
   133		k0 := len(z) - 1
   134		for j := len(y) - 1; j >= 0; j-- {
   135			d := int(y[j])
   136			if d != 0 {
   137				k := k0
   138				carry := 0
   139				for i := len(x) - 1; i >= 0; i-- {
   140					t := int(z[k]) + int(x[i])*d + carry
   141					z[k], carry = byte(t), t>>8
   142					k--
   143				}
   144				z[k] = byte(carry)
   145			}
   146			k0--
   147		}
   148	
   149		// normalize (remove leading 0's)
   150		i := 0
   151		for i < len(z) && z[i] == 0 {
   152			i++
   153		}
   154	
   155		return z[i:]
   156	}
   157	
   158	func checkMul(a, b []byte) bool {
   159		var x, y, z1 Int
   160		x.SetBytes(a)
   161		y.SetBytes(b)
   162		z1.Mul(&x, &y)
   163	
   164		var z2 Int
   165		z2.SetBytes(mulBytes(a, b))
   166	
   167		return z1.Cmp(&z2) == 0
   168	}
   169	
   170	func TestMul(t *testing.T) {
   171		if err := quick.Check(checkMul, nil); err != nil {
   172			t.Error(err)
   173		}
   174	}
   175	
   176	var mulRangesZ = []struct {
   177		a, b int64
   178		prod string
   179	}{
   180		// entirely positive ranges are covered by mulRangesN
   181		{-1, 1, "0"},
   182		{-2, -1, "2"},
   183		{-3, -2, "6"},
   184		{-3, -1, "-6"},
   185		{1, 3, "6"},
   186		{-10, -10, "-10"},
   187		{0, -1, "1"},                      // empty range
   188		{-1, -100, "1"},                   // empty range
   189		{-1, 1, "0"},                      // range includes 0
   190		{-1e9, 0, "0"},                    // range includes 0
   191		{-1e9, 1e9, "0"},                  // range includes 0
   192		{-10, -1, "3628800"},              // 10!
   193		{-20, -2, "-2432902008176640000"}, // -20!
   194		{-99, -1,
   195			"-933262154439441526816992388562667004907159682643816214685929" +
   196				"638952175999932299156089414639761565182862536979208272237582" +
   197				"511852109168640000000000000000000000", // -99!
   198		},
   199	}
   200	
   201	func TestMulRangeZ(t *testing.T) {
   202		var tmp Int
   203		// test entirely positive ranges
   204		for i, r := range mulRangesN {
   205			prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
   206			if prod != r.prod {
   207				t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
   208			}
   209		}
   210		// test other ranges
   211		for i, r := range mulRangesZ {
   212			prod := tmp.MulRange(r.a, r.b).String()
   213			if prod != r.prod {
   214				t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
   215			}
   216		}
   217	}
   218	
   219	var stringTests = []struct {
   220		in   string
   221		out  string
   222		base int
   223		val  int64
   224		ok   bool
   225	}{
   226		{in: "", ok: false},
   227		{in: "a", ok: false},
   228		{in: "z", ok: false},
   229		{in: "+", ok: false},
   230		{in: "-", ok: false},
   231		{in: "0b", ok: false},
   232		{in: "0x", ok: false},
   233		{in: "2", base: 2, ok: false},
   234		{in: "0b2", base: 0, ok: false},
   235		{in: "08", ok: false},
   236		{in: "8", base: 8, ok: false},
   237		{in: "0xg", base: 0, ok: false},
   238		{in: "g", base: 16, ok: false},
   239		{"0", "0", 0, 0, true},
   240		{"0", "0", 10, 0, true},
   241		{"0", "0", 16, 0, true},
   242		{"+0", "0", 0, 0, true},
   243		{"-0", "0", 0, 0, true},
   244		{"10", "10", 0, 10, true},
   245		{"10", "10", 10, 10, true},
   246		{"10", "10", 16, 16, true},
   247		{"-10", "-10", 16, -16, true},
   248		{"+10", "10", 16, 16, true},
   249		{"0x10", "16", 0, 16, true},
   250		{in: "0x10", base: 16, ok: false},
   251		{"-0x10", "-16", 0, -16, true},
   252		{"+0x10", "16", 0, 16, true},
   253		{"00", "0", 0, 0, true},
   254		{"0", "0", 8, 0, true},
   255		{"07", "7", 0, 7, true},
   256		{"7", "7", 8, 7, true},
   257		{"023", "19", 0, 19, true},
   258		{"23", "23", 8, 19, true},
   259		{"cafebabe", "cafebabe", 16, 0xcafebabe, true},
   260		{"0b0", "0", 0, 0, true},
   261		{"-111", "-111", 2, -7, true},
   262		{"-0b111", "-7", 0, -7, true},
   263		{"0b1001010111", "599", 0, 0x257, true},
   264		{"1001010111", "1001010111", 2, 0x257, true},
   265	}
   266	
   267	func format(base int) string {
   268		switch base {
   269		case 2:
   270			return "%b"
   271		case 8:
   272			return "%o"
   273		case 16:
   274			return "%x"
   275		}
   276		return "%d"
   277	}
   278	
   279	func TestGetString(t *testing.T) {
   280		z := new(Int)
   281		for i, test := range stringTests {
   282			if !test.ok {
   283				continue
   284			}
   285			z.SetInt64(test.val)
   286	
   287			if test.base == 10 {
   288				s := z.String()
   289				if s != test.out {
   290					t.Errorf("#%da got %s; want %s", i, s, test.out)
   291				}
   292			}
   293	
   294			s := fmt.Sprintf(format(test.base), z)
   295			if s != test.out {
   296				t.Errorf("#%db got %s; want %s", i, s, test.out)
   297			}
   298		}
   299	}
   300	
   301	func TestSetString(t *testing.T) {
   302		tmp := new(Int)
   303		for i, test := range stringTests {
   304			n1, ok1 := new(Int).SetString(test.in, test.base)
   305			n2, ok2 := tmp.SetString(test.in, test.base)
   306			expected := NewInt(test.val)
   307			if ok1 != test.ok || ok2 != test.ok {
   308				t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
   309				continue
   310			}
   311			if !ok1 || !ok2 {
   312				continue
   313			}
   314	
   315			if ok1 && !isNormalized(n1) {
   316				t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1)
   317			}
   318			if ok2 && !isNormalized(n2) {
   319				t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2)
   320			}
   321	
   322			if n1.Cmp(expected) != 0 {
   323				t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
   324			}
   325			if n2.Cmp(expected) != 0 {
   326				t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
   327			}
   328		}
   329	}
   330	
   331	var formatTests = []struct {
   332		input  string
   333		format string
   334		output string
   335	}{
   336		{"<nil>", "%x", "<nil>"},
   337		{"<nil>", "%#x", "<nil>"},
   338		{"<nil>", "%#y", "%!y(big.Int=<nil>)"},
   339	
   340		{"10", "%b", "1010"},
   341		{"10", "%o", "12"},
   342		{"10", "%d", "10"},
   343		{"10", "%v", "10"},
   344		{"10", "%x", "a"},
   345		{"10", "%X", "A"},
   346		{"-10", "%X", "-A"},
   347		{"10", "%y", "%!y(big.Int=10)"},
   348		{"-10", "%y", "%!y(big.Int=-10)"},
   349	
   350		{"10", "%#b", "1010"},
   351		{"10", "%#o", "012"},
   352		{"10", "%#d", "10"},
   353		{"10", "%#v", "10"},
   354		{"10", "%#x", "0xa"},
   355		{"10", "%#X", "0XA"},
   356		{"-10", "%#X", "-0XA"},
   357		{"10", "%#y", "%!y(big.Int=10)"},
   358		{"-10", "%#y", "%!y(big.Int=-10)"},
   359	
   360		{"1234", "%d", "1234"},
   361		{"1234", "%3d", "1234"},
   362		{"1234", "%4d", "1234"},
   363		{"-1234", "%d", "-1234"},
   364		{"1234", "% 5d", " 1234"},
   365		{"1234", "%+5d", "+1234"},
   366		{"1234", "%-5d", "1234 "},
   367		{"1234", "%x", "4d2"},
   368		{"1234", "%X", "4D2"},
   369		{"-1234", "%3x", "-4d2"},
   370		{"-1234", "%4x", "-4d2"},
   371		{"-1234", "%5x", " -4d2"},
   372		{"-1234", "%-5x", "-4d2 "},
   373		{"1234", "%03d", "1234"},
   374		{"1234", "%04d", "1234"},
   375		{"1234", "%05d", "01234"},
   376		{"1234", "%06d", "001234"},
   377		{"-1234", "%06d", "-01234"},
   378		{"1234", "%+06d", "+01234"},
   379		{"1234", "% 06d", " 01234"},
   380		{"1234", "%-6d", "1234  "},
   381		{"1234", "%-06d", "1234  "},
   382		{"-1234", "%-06d", "-1234 "},
   383	
   384		{"1234", "%.3d", "1234"},
   385		{"1234", "%.4d", "1234"},
   386		{"1234", "%.5d", "01234"},
   387		{"1234", "%.6d", "001234"},
   388		{"-1234", "%.3d", "-1234"},
   389		{"-1234", "%.4d", "-1234"},
   390		{"-1234", "%.5d", "-01234"},
   391		{"-1234", "%.6d", "-001234"},
   392	
   393		{"1234", "%8.3d", "    1234"},
   394		{"1234", "%8.4d", "    1234"},
   395		{"1234", "%8.5d", "   01234"},
   396		{"1234", "%8.6d", "  001234"},
   397		{"-1234", "%8.3d", "   -1234"},
   398		{"-1234", "%8.4d", "   -1234"},
   399		{"-1234", "%8.5d", "  -01234"},
   400		{"-1234", "%8.6d", " -001234"},
   401	
   402		{"1234", "%+8.3d", "   +1234"},
   403		{"1234", "%+8.4d", "   +1234"},
   404		{"1234", "%+8.5d", "  +01234"},
   405		{"1234", "%+8.6d", " +001234"},
   406		{"-1234", "%+8.3d", "   -1234"},
   407		{"-1234", "%+8.4d", "   -1234"},
   408		{"-1234", "%+8.5d", "  -01234"},
   409		{"-1234", "%+8.6d", " -001234"},
   410	
   411		{"1234", "% 8.3d", "    1234"},
   412		{"1234", "% 8.4d", "    1234"},
   413		{"1234", "% 8.5d", "   01234"},
   414		{"1234", "% 8.6d", "  001234"},
   415		{"-1234", "% 8.3d", "   -1234"},
   416		{"-1234", "% 8.4d", "   -1234"},
   417		{"-1234", "% 8.5d", "  -01234"},
   418		{"-1234", "% 8.6d", " -001234"},
   419	
   420		{"1234", "%.3x", "4d2"},
   421		{"1234", "%.4x", "04d2"},
   422		{"1234", "%.5x", "004d2"},
   423		{"1234", "%.6x", "0004d2"},
   424		{"-1234", "%.3x", "-4d2"},
   425		{"-1234", "%.4x", "-04d2"},
   426		{"-1234", "%.5x", "-004d2"},
   427		{"-1234", "%.6x", "-0004d2"},
   428	
   429		{"1234", "%8.3x", "     4d2"},
   430		{"1234", "%8.4x", "    04d2"},
   431		{"1234", "%8.5x", "   004d2"},
   432		{"1234", "%8.6x", "  0004d2"},
   433		{"-1234", "%8.3x", "    -4d2"},
   434		{"-1234", "%8.4x", "   -04d2"},
   435		{"-1234", "%8.5x", "  -004d2"},
   436		{"-1234", "%8.6x", " -0004d2"},
   437	
   438		{"1234", "%+8.3x", "    +4d2"},
   439		{"1234", "%+8.4x", "   +04d2"},
   440		{"1234", "%+8.5x", "  +004d2"},
   441		{"1234", "%+8.6x", " +0004d2"},
   442		{"-1234", "%+8.3x", "    -4d2"},
   443		{"-1234", "%+8.4x", "   -04d2"},
   444		{"-1234", "%+8.5x", "  -004d2"},
   445		{"-1234", "%+8.6x", " -0004d2"},
   446	
   447		{"1234", "% 8.3x", "     4d2"},
   448		{"1234", "% 8.4x", "    04d2"},
   449		{"1234", "% 8.5x", "   004d2"},
   450		{"1234", "% 8.6x", "  0004d2"},
   451		{"1234", "% 8.7x", " 00004d2"},
   452		{"1234", "% 8.8x", " 000004d2"},
   453		{"-1234", "% 8.3x", "    -4d2"},
   454		{"-1234", "% 8.4x", "   -04d2"},
   455		{"-1234", "% 8.5x", "  -004d2"},
   456		{"-1234", "% 8.6x", " -0004d2"},
   457		{"-1234", "% 8.7x", "-00004d2"},
   458		{"-1234", "% 8.8x", "-000004d2"},
   459	
   460		{"1234", "%-8.3d", "1234    "},
   461		{"1234", "%-8.4d", "1234    "},
   462		{"1234", "%-8.5d", "01234   "},
   463		{"1234", "%-8.6d", "001234  "},
   464		{"1234", "%-8.7d", "0001234 "},
   465		{"1234", "%-8.8d", "00001234"},
   466		{"-1234", "%-8.3d", "-1234   "},
   467		{"-1234", "%-8.4d", "-1234   "},
   468		{"-1234", "%-8.5d", "-01234  "},
   469		{"-1234", "%-8.6d", "-001234 "},
   470		{"-1234", "%-8.7d", "-0001234"},
   471		{"-1234", "%-8.8d", "-00001234"},
   472	
   473		{"16777215", "%b", "111111111111111111111111"}, // 2**24 - 1
   474	
   475		{"0", "%.d", ""},
   476		{"0", "%.0d", ""},
   477		{"0", "%3.d", ""},
   478	}
   479	
   480	func TestFormat(t *testing.T) {
   481		for i, test := range formatTests {
   482			var x *Int
   483			if test.input != "<nil>" {
   484				var ok bool
   485				x, ok = new(Int).SetString(test.input, 0)
   486				if !ok {
   487					t.Errorf("#%d failed reading input %s", i, test.input)
   488				}
   489			}
   490			output := fmt.Sprintf(test.format, x)
   491			if output != test.output {
   492				t.Errorf("#%d got %q; want %q, {%q, %q, %q}", i, output, test.output, test.input, test.format, test.output)
   493			}
   494		}
   495	}
   496	
   497	var scanTests = []struct {
   498		input     string
   499		format    string
   500		output    string
   501		remaining int
   502	}{
   503		{"1010", "%b", "10", 0},
   504		{"0b1010", "%v", "10", 0},
   505		{"12", "%o", "10", 0},
   506		{"012", "%v", "10", 0},
   507		{"10", "%d", "10", 0},
   508		{"10", "%v", "10", 0},
   509		{"a", "%x", "10", 0},
   510		{"0xa", "%v", "10", 0},
   511		{"A", "%X", "10", 0},
   512		{"-A", "%X", "-10", 0},
   513		{"+0b1011001", "%v", "89", 0},
   514		{"0xA", "%v", "10", 0},
   515		{"0 ", "%v", "0", 1},
   516		{"2+3", "%v", "2", 2},
   517		{"0XABC 12", "%v", "2748", 3},
   518	}
   519	
   520	func TestScan(t *testing.T) {
   521		var buf bytes.Buffer
   522		for i, test := range scanTests {
   523			x := new(Int)
   524			buf.Reset()
   525			buf.WriteString(test.input)
   526			if _, err := fmt.Fscanf(&buf, test.format, x); err != nil {
   527				t.Errorf("#%d error: %s", i, err.String())
   528			}
   529			if x.String() != test.output {
   530				t.Errorf("#%d got %s; want %s", i, x.String(), test.output)
   531			}
   532			if buf.Len() != test.remaining {
   533				t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining)
   534			}
   535		}
   536	}
   537	
   538	// Examples from the Go Language Spec, section "Arithmetic operators"
   539	var divisionSignsTests = []struct {
   540		x, y int64
   541		q, r int64 // T-division
   542		d, m int64 // Euclidian division
   543	}{
   544		{5, 3, 1, 2, 1, 2},
   545		{-5, 3, -1, -2, -2, 1},
   546		{5, -3, -1, 2, -1, 2},
   547		{-5, -3, 1, -2, 2, 1},
   548		{1, 2, 0, 1, 0, 1},
   549		{8, 4, 2, 0, 2, 0},
   550	}
   551	
   552	func TestDivisionSigns(t *testing.T) {
   553		for i, test := range divisionSignsTests {
   554			x := NewInt(test.x)
   555			y := NewInt(test.y)
   556			q := NewInt(test.q)
   557			r := NewInt(test.r)
   558			d := NewInt(test.d)
   559			m := NewInt(test.m)
   560	
   561			q1 := new(Int).Quo(x, y)
   562			r1 := new(Int).Rem(x, y)
   563			if !isNormalized(q1) {
   564				t.Errorf("#%d Quo: %v is not normalized", i, *q1)
   565			}
   566			if !isNormalized(r1) {
   567				t.Errorf("#%d Rem: %v is not normalized", i, *r1)
   568			}
   569			if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
   570				t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
   571			}
   572	
   573			q2, r2 := new(Int).QuoRem(x, y, new(Int))
   574			if !isNormalized(q2) {
   575				t.Errorf("#%d Quo: %v is not normalized", i, *q2)
   576			}
   577			if !isNormalized(r2) {
   578				t.Errorf("#%d Rem: %v is not normalized", i, *r2)
   579			}
   580			if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
   581				t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
   582			}
   583	
   584			d1 := new(Int).Div(x, y)
   585			m1 := new(Int).Mod(x, y)
   586			if !isNormalized(d1) {
   587				t.Errorf("#%d Div: %v is not normalized", i, *d1)
   588			}
   589			if !isNormalized(m1) {
   590				t.Errorf("#%d Mod: %v is not normalized", i, *m1)
   591			}
   592			if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
   593				t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
   594			}
   595	
   596			d2, m2 := new(Int).DivMod(x, y, new(Int))
   597			if !isNormalized(d2) {
   598				t.Errorf("#%d Div: %v is not normalized", i, *d2)
   599			}
   600			if !isNormalized(m2) {
   601				t.Errorf("#%d Mod: %v is not normalized", i, *m2)
   602			}
   603			if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
   604				t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
   605			}
   606		}
   607	}
   608	
   609	func checkSetBytes(b []byte) bool {
   610		hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
   611		hex2 := hex.EncodeToString(b)
   612	
   613		for len(hex1) < len(hex2) {
   614			hex1 = "0" + hex1
   615		}
   616	
   617		for len(hex1) > len(hex2) {
   618			hex2 = "0" + hex2
   619		}
   620	
   621		return hex1 == hex2
   622	}
   623	
   624	func TestSetBytes(t *testing.T) {
   625		if err := quick.Check(checkSetBytes, nil); err != nil {
   626			t.Error(err)
   627		}
   628	}
   629	
   630	func checkBytes(b []byte) bool {
   631		b2 := new(Int).SetBytes(b).Bytes()
   632		return bytes.Compare(b, b2) == 0
   633	}
   634	
   635	func TestBytes(t *testing.T) {
   636		if err := quick.Check(checkSetBytes, nil); err != nil {
   637			t.Error(err)
   638		}
   639	}
   640	
   641	func checkQuo(x, y []byte) bool {
   642		u := new(Int).SetBytes(x)
   643		v := new(Int).SetBytes(y)
   644	
   645		if len(v.abs) == 0 {
   646			return true
   647		}
   648	
   649		r := new(Int)
   650		q, r := new(Int).QuoRem(u, v, r)
   651	
   652		if r.Cmp(v) >= 0 {
   653			return false
   654		}
   655	
   656		uprime := new(Int).Set(q)
   657		uprime.Mul(uprime, v)
   658		uprime.Add(uprime, r)
   659	
   660		return uprime.Cmp(u) == 0
   661	}
   662	
   663	var quoTests = []struct {
   664		x, y string
   665		q, r string
   666	}{
   667		{
   668			"476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
   669			"9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
   670			"50911",
   671			"1",
   672		},
   673		{
   674			"11510768301994997771168",
   675			"1328165573307167369775",
   676			"8",
   677			"885443715537658812968",
   678		},
   679	}
   680	
   681	func TestQuo(t *testing.T) {
   682		if err := quick.Check(checkQuo, nil); err != nil {
   683			t.Error(err)
   684		}
   685	
   686		for i, test := range quoTests {
   687			x, _ := new(Int).SetString(test.x, 10)
   688			y, _ := new(Int).SetString(test.y, 10)
   689			expectedQ, _ := new(Int).SetString(test.q, 10)
   690			expectedR, _ := new(Int).SetString(test.r, 10)
   691	
   692			r := new(Int)
   693			q, r := new(Int).QuoRem(x, y, r)
   694	
   695			if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
   696				t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
   697			}
   698		}
   699	}
   700	
   701	func TestQuoStepD6(t *testing.T) {
   702		// See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
   703		// a code path which only triggers 1 in 10^{-19} cases.
   704	
   705		u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
   706		v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
   707	
   708		r := new(Int)
   709		q, r := new(Int).QuoRem(u, v, r)
   710		const expectedQ64 = "18446744073709551613"
   711		const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
   712		const expectedQ32 = "4294967293"
   713		const expectedR32 = "39614081266355540837921718287"
   714		if q.String() != expectedQ64 && q.String() != expectedQ32 ||
   715			r.String() != expectedR64 && r.String() != expectedR32 {
   716			t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
   717		}
   718	}
   719	
   720	var bitLenTests = []struct {
   721		in  string
   722		out int
   723	}{
   724		{"-1", 1},
   725		{"0", 0},
   726		{"1", 1},
   727		{"2", 2},
   728		{"4", 3},
   729		{"0xabc", 12},
   730		{"0x8000", 16},
   731		{"0x80000000", 32},
   732		{"0x800000000000", 48},
   733		{"0x8000000000000000", 64},
   734		{"0x80000000000000000000", 80},
   735		{"-0x4000000000000000000000", 87},
   736	}
   737	
   738	func TestBitLen(t *testing.T) {
   739		for i, test := range bitLenTests {
   740			x, ok := new(Int).SetString(test.in, 0)
   741			if !ok {
   742				t.Errorf("#%d test input invalid: %s", i, test.in)
   743				continue
   744			}
   745	
   746			if n := x.BitLen(); n != test.out {
   747				t.Errorf("#%d got %d want %d", i, n, test.out)
   748			}
   749		}
   750	}
   751	
   752	var expTests = []struct {
   753		x, y, m string
   754		out     string
   755	}{
   756		{"5", "0", "", "1"},
   757		{"-5", "0", "", "-1"},
   758		{"5", "1", "", "5"},
   759		{"-5", "1", "", "-5"},
   760		{"-2", "3", "2", "0"},
   761		{"5", "2", "", "25"},
   762		{"1", "65537", "2", "1"},
   763		{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
   764		{"0x8000000000000000", "2", "6719", "4944"},
   765		{"0x8000000000000000", "3", "6719", "5447"},
   766		{"0x8000000000000000", "1000", "6719", "1603"},
   767		{"0x8000000000000000", "1000000", "6719", "3199"},
   768		{
   769			"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
   770			"298472983472983471903246121093472394872319615612417471234712061",
   771			"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
   772			"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
   773		},
   774	}
   775	
   776	func TestExp(t *testing.T) {
   777		for i, test := range expTests {
   778			x, ok1 := new(Int).SetString(test.x, 0)
   779			y, ok2 := new(Int).SetString(test.y, 0)
   780			out, ok3 := new(Int).SetString(test.out, 0)
   781	
   782			var ok4 bool
   783			var m *Int
   784	
   785			if len(test.m) == 0 {
   786				m, ok4 = nil, true
   787			} else {
   788				m, ok4 = new(Int).SetString(test.m, 0)
   789			}
   790	
   791			if !ok1 || !ok2 || !ok3 || !ok4 {
   792				t.Errorf("#%d: error in input", i)
   793				continue
   794			}
   795	
   796			z := y.Exp(x, y, m)
   797			if !isNormalized(z) {
   798				t.Errorf("#%d: %v is not normalized", i, *z)
   799			}
   800			if z.Cmp(out) != 0 {
   801				t.Errorf("#%d: got %s want %s", i, z, out)
   802			}
   803		}
   804	}
   805	
   806	func checkGcd(aBytes, bBytes []byte) bool {
   807		a := new(Int).SetBytes(aBytes)
   808		b := new(Int).SetBytes(bBytes)
   809	
   810		x := new(Int)
   811		y := new(Int)
   812		d := new(Int)
   813	
   814		GcdInt(d, x, y, a, b)
   815		x.Mul(x, a)
   816		y.Mul(y, b)
   817		x.Add(x, y)
   818	
   819		return x.Cmp(d) == 0
   820	}
   821	
   822	var gcdTests = []struct {
   823		a, b    int64
   824		d, x, y int64
   825	}{
   826		{120, 23, 1, -9, 47},
   827	}
   828	
   829	func TestGcd(t *testing.T) {
   830		for i, test := range gcdTests {
   831			a := NewInt(test.a)
   832			b := NewInt(test.b)
   833	
   834			x := new(Int)
   835			y := new(Int)
   836			d := new(Int)
   837	
   838			expectedX := NewInt(test.x)
   839			expectedY := NewInt(test.y)
   840			expectedD := NewInt(test.d)
   841	
   842			GcdInt(d, x, y, a, b)
   843	
   844			if expectedX.Cmp(x) != 0 ||
   845				expectedY.Cmp(y) != 0 ||
   846				expectedD.Cmp(d) != 0 {
   847				t.Errorf("#%d got (%s %s %s) want (%s %s %s)", i, x, y, d, expectedX, expectedY, expectedD)
   848			}
   849		}
   850	
   851		quick.Check(checkGcd, nil)
   852	}
   853	
   854	var primes = []string{
   855		"2",
   856		"3",
   857		"5",
   858		"7",
   859		"11",
   860	
   861		"13756265695458089029",
   862		"13496181268022124907",
   863		"10953742525620032441",
   864		"17908251027575790097",
   865	
   866		// http://code.google.com/p/go/issues/detail?id=638
   867		"18699199384836356663",
   868	
   869		"98920366548084643601728869055592650835572950932266967461790948584315647051443",
   870		"94560208308847015747498523884063394671606671904944666360068158221458669711639",
   871	
   872		// http://primes.utm.edu/lists/small/small3.html
   873		"449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
   874		"230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
   875		"5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
   876		"203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
   877	}
   878	
   879	var composites = []string{
   880		"21284175091214687912771199898307297748211672914763848041968395774954376176754",
   881		"6084766654921918907427900243509372380954290099172559290432744450051395395951",
   882		"84594350493221918389213352992032324280367711247940675652888030554255915464401",
   883		"82793403787388584738507275144194252681",
   884	}
   885	
   886	func TestProbablyPrime(t *testing.T) {
   887		nreps := 20
   888		if testing.Short() {
   889			nreps = 1
   890		}
   891		for i, s := range primes {
   892			p, _ := new(Int).SetString(s, 10)
   893			if !ProbablyPrime(p, nreps) {
   894				t.Errorf("#%d prime found to be non-prime (%s)", i, s)
   895			}
   896		}
   897	
   898		for i, s := range composites {
   899			c, _ := new(Int).SetString(s, 10)
   900			if ProbablyPrime(c, nreps) {
   901				t.Errorf("#%d composite found to be prime (%s)", i, s)
   902			}
   903			if testing.Short() {
   904				break
   905			}
   906		}
   907	}
   908	
   909	type intShiftTest struct {
   910		in    string
   911		shift uint
   912		out   string
   913	}
   914	
   915	var rshTests = []intShiftTest{
   916		{"0", 0, "0"},
   917		{"-0", 0, "0"},
   918		{"0", 1, "0"},
   919		{"0", 2, "0"},
   920		{"1", 0, "1"},
   921		{"1", 1, "0"},
   922		{"1", 2, "0"},
   923		{"2", 0, "2"},
   924		{"2", 1, "1"},
   925		{"-1", 0, "-1"},
   926		{"-1", 1, "-1"},
   927		{"-1", 10, "-1"},
   928		{"-100", 2, "-25"},
   929		{"-100", 3, "-13"},
   930		{"-100", 100, "-1"},
   931		{"4294967296", 0, "4294967296"},
   932		{"4294967296", 1, "2147483648"},
   933		{"4294967296", 2, "1073741824"},
   934		{"18446744073709551616", 0, "18446744073709551616"},
   935		{"18446744073709551616", 1, "9223372036854775808"},
   936		{"18446744073709551616", 2, "4611686018427387904"},
   937		{"18446744073709551616", 64, "1"},
   938		{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
   939		{"340282366920938463463374607431768211456", 128, "1"},
   940	}
   941	
   942	func TestRsh(t *testing.T) {
   943		for i, test := range rshTests {
   944			in, _ := new(Int).SetString(test.in, 10)
   945			expected, _ := new(Int).SetString(test.out, 10)
   946			out := new(Int).Rsh(in, test.shift)
   947	
   948			if !isNormalized(out) {
   949				t.Errorf("#%d: %v is not normalized", i, *out)
   950			}
   951			if out.Cmp(expected) != 0 {
   952				t.Errorf("#%d: got %s want %s", i, out, expected)
   953			}
   954		}
   955	}
   956	
   957	func TestRshSelf(t *testing.T) {
   958		for i, test := range rshTests {
   959			z, _ := new(Int).SetString(test.in, 10)
   960			expected, _ := new(Int).SetString(test.out, 10)
   961			z.Rsh(z, test.shift)
   962	
   963			if !isNormalized(z) {
   964				t.Errorf("#%d: %v is not normalized", i, *z)
   965			}
   966			if z.Cmp(expected) != 0 {
   967				t.Errorf("#%d: got %s want %s", i, z, expected)
   968			}
   969		}
   970	}
   971	
   972	var lshTests = []intShiftTest{
   973		{"0", 0, "0"},
   974		{"0", 1, "0"},
   975		{"0", 2, "0"},
   976		{"1", 0, "1"},
   977		{"1", 1, "2"},
   978		{"1", 2, "4"},
   979		{"2", 0, "2"},
   980		{"2", 1, "4"},
   981		{"2", 2, "8"},
   982		{"-87", 1, "-174"},
   983		{"4294967296", 0, "4294967296"},
   984		{"4294967296", 1, "8589934592"},
   985		{"4294967296", 2, "17179869184"},
   986		{"18446744073709551616", 0, "18446744073709551616"},
   987		{"9223372036854775808", 1, "18446744073709551616"},
   988		{"4611686018427387904", 2, "18446744073709551616"},
   989		{"1", 64, "18446744073709551616"},
   990		{"18446744073709551616", 64, "340282366920938463463374607431768211456"},
   991		{"1", 128, "340282366920938463463374607431768211456"},
   992	}
   993	
   994	func TestLsh(t *testing.T) {
   995		for i, test := range lshTests {
   996			in, _ := new(Int).SetString(test.in, 10)
   997			expected, _ := new(Int).SetString(test.out, 10)
   998			out := new(Int).Lsh(in, test.shift)
   999	
  1000			if !isNormalized(out) {
  1001				t.Errorf("#%d: %v is not normalized", i, *out)
  1002			}
  1003			if out.Cmp(expected) != 0 {
  1004				t.Errorf("#%d: got %s want %s", i, out, expected)
  1005			}
  1006		}
  1007	}
  1008	
  1009	func TestLshSelf(t *testing.T) {
  1010		for i, test := range lshTests {
  1011			z, _ := new(Int).SetString(test.in, 10)
  1012			expected, _ := new(Int).SetString(test.out, 10)
  1013			z.Lsh(z, test.shift)
  1014	
  1015			if !isNormalized(z) {
  1016				t.Errorf("#%d: %v is not normalized", i, *z)
  1017			}
  1018			if z.Cmp(expected) != 0 {
  1019				t.Errorf("#%d: got %s want %s", i, z, expected)
  1020			}
  1021		}
  1022	}
  1023	
  1024	func TestLshRsh(t *testing.T) {
  1025		for i, test := range rshTests {
  1026			in, _ := new(Int).SetString(test.in, 10)
  1027			out := new(Int).Lsh(in, test.shift)
  1028			out = out.Rsh(out, test.shift)
  1029	
  1030			if !isNormalized(out) {
  1031				t.Errorf("#%d: %v is not normalized", i, *out)
  1032			}
  1033			if in.Cmp(out) != 0 {
  1034				t.Errorf("#%d: got %s want %s", i, out, in)
  1035			}
  1036		}
  1037		for i, test := range lshTests {
  1038			in, _ := new(Int).SetString(test.in, 10)
  1039			out := new(Int).Lsh(in, test.shift)
  1040			out.Rsh(out, test.shift)
  1041	
  1042			if !isNormalized(out) {
  1043				t.Errorf("#%d: %v is not normalized", i, *out)
  1044			}
  1045			if in.Cmp(out) != 0 {
  1046				t.Errorf("#%d: got %s want %s", i, out, in)
  1047			}
  1048		}
  1049	}
  1050	
  1051	var int64Tests = []int64{
  1052		0,
  1053		1,
  1054		-1,
  1055		4294967295,
  1056		-4294967295,
  1057		4294967296,
  1058		-4294967296,
  1059		9223372036854775807,
  1060		-9223372036854775807,
  1061		-9223372036854775808,
  1062	}
  1063	
  1064	func TestInt64(t *testing.T) {
  1065		for i, testVal := range int64Tests {
  1066			in := NewInt(testVal)
  1067			out := in.Int64()
  1068	
  1069			if out != testVal {
  1070				t.Errorf("#%d got %d want %d", i, out, testVal)
  1071			}
  1072		}
  1073	}
  1074	
  1075	var bitwiseTests = []struct {
  1076		x, y                 string
  1077		and, or, xor, andNot string
  1078	}{
  1079		{"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
  1080		{"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
  1081		{"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
  1082		{"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
  1083		{"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
  1084		{"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
  1085		{"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
  1086		{"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
  1087		{"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
  1088		{"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
  1089		{"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
  1090		{"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
  1091		{"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
  1092		{
  1093			"0x1000009dc6e3d9822cba04129bcbe3401",
  1094			"0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
  1095			"0x1000001186210100001000009048c2001",
  1096			"0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
  1097			"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
  1098			"0x8c40c2d8822caa04120b8321400",
  1099		},
  1100		{
  1101			"0x1000009dc6e3d9822cba04129bcbe3401",
  1102			"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
  1103			"0x8c40c2d8822caa04120b8321401",
  1104			"-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
  1105			"-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
  1106			"0x1000001186210100001000009048c2000",
  1107		},
  1108		{
  1109			"-0x1000009dc6e3d9822cba04129bcbe3401",
  1110			"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
  1111			"-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
  1112			"-0x1000001186210100001000009048c2001",
  1113			"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
  1114			"0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
  1115		},
  1116	}
  1117	
  1118	type bitFun func(z, x, y *Int) *Int
  1119	
  1120	func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
  1121		expected := new(Int)
  1122		expected.SetString(exp, 0)
  1123	
  1124		out := f(new(Int), x, y)
  1125		if out.Cmp(expected) != 0 {
  1126			t.Errorf("%s: got %s want %s", msg, out, expected)
  1127		}
  1128	}
  1129	
  1130	func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
  1131		self := new(Int)
  1132		self.Set(x)
  1133		expected := new(Int)
  1134		expected.SetString(exp, 0)
  1135	
  1136		self = f(self, self, y)
  1137		if self.Cmp(expected) != 0 {
  1138			t.Errorf("%s: got %s want %s", msg, self, expected)
  1139		}
  1140	}
  1141	
  1142	func altBit(x *Int, i int) uint {
  1143		z := new(Int).Rsh(x, uint(i))
  1144		z = z.And(z, NewInt(1))
  1145		if z.Cmp(new(Int)) != 0 {
  1146			return 1
  1147		}
  1148		return 0
  1149	}
  1150	
  1151	func altSetBit(z *Int, x *Int, i int, b uint) *Int {
  1152		one := NewInt(1)
  1153		m := one.Lsh(one, uint(i))
  1154		switch b {
  1155		case 1:
  1156			return z.Or(x, m)
  1157		case 0:
  1158			return z.AndNot(x, m)
  1159		}
  1160		panic("set bit is not 0 or 1")
  1161	}
  1162	
  1163	func testBitset(t *testing.T, x *Int) {
  1164		n := x.BitLen()
  1165		z := new(Int).Set(x)
  1166		z1 := new(Int).Set(x)
  1167		for i := 0; i < n+10; i++ {
  1168			old := z.Bit(i)
  1169			old1 := altBit(z1, i)
  1170			if old != old1 {
  1171				t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
  1172			}
  1173			z := new(Int).SetBit(z, i, 1)
  1174			z1 := altSetBit(new(Int), z1, i, 1)
  1175			if z.Bit(i) == 0 {
  1176				t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
  1177			}
  1178			if z.Cmp(z1) != 0 {
  1179				t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
  1180			}
  1181			z.SetBit(z, i, 0)
  1182			altSetBit(z1, z1, i, 0)
  1183			if z.Bit(i) != 0 {
  1184				t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
  1185			}
  1186			if z.Cmp(z1) != 0 {
  1187				t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
  1188			}
  1189			altSetBit(z1, z1, i, old)
  1190			z.SetBit(z, i, old)
  1191			if z.Cmp(z1) != 0 {
  1192				t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
  1193			}
  1194		}
  1195		if z.Cmp(x) != 0 {
  1196			t.Errorf("bitset: got %s want %s", z, x)
  1197		}
  1198	}
  1199	
  1200	var bitsetTests = []struct {
  1201		x string
  1202		i int
  1203		b uint
  1204	}{
  1205		{"0", 0, 0},
  1206		{"0", 200, 0},
  1207		{"1", 0, 1},
  1208		{"1", 1, 0},
  1209		{"-1", 0, 1},
  1210		{"-1", 200, 1},
  1211		{"0x2000000000000000000000000000", 108, 0},
  1212		{"0x2000000000000000000000000000", 109, 1},
  1213		{"0x2000000000000000000000000000", 110, 0},
  1214		{"-0x2000000000000000000000000001", 108, 1},
  1215		{"-0x2000000000000000000000000001", 109, 0},
  1216		{"-0x2000000000000000000000000001", 110, 1},
  1217	}
  1218	
  1219	func TestBitSet(t *testing.T) {
  1220		for _, test := range bitwiseTests {
  1221			x := new(Int)
  1222			x.SetString(test.x, 0)
  1223			testBitset(t, x)
  1224			x = new(Int)
  1225			x.SetString(test.y, 0)
  1226			testBitset(t, x)
  1227		}
  1228		for i, test := range bitsetTests {
  1229			x := new(Int)
  1230			x.SetString(test.x, 0)
  1231			b := x.Bit(test.i)
  1232			if b != test.b {
  1233	
  1234				t.Errorf("#%d want %v got %v", i, test.b, b)
  1235			}
  1236		}
  1237	}
  1238	
  1239	func BenchmarkBitset(b *testing.B) {
  1240		z := new(Int)
  1241		z.SetBit(z, 512, 1)
  1242		b.ResetTimer()
  1243		b.StartTimer()
  1244		for i := b.N - 1; i >= 0; i-- {
  1245			z.SetBit(z, i&512, 1)
  1246		}
  1247	}
  1248	
  1249	func BenchmarkBitsetNeg(b *testing.B) {
  1250		z := NewInt(-1)
  1251		z.SetBit(z, 512, 0)
  1252		b.ResetTimer()
  1253		b.StartTimer()
  1254		for i := b.N - 1; i >= 0; i-- {
  1255			z.SetBit(z, i&512, 0)
  1256		}
  1257	}
  1258	
  1259	func BenchmarkBitsetOrig(b *testing.B) {
  1260		z := new(Int)
  1261		altSetBit(z, z, 512, 1)
  1262		b.ResetTimer()
  1263		b.StartTimer()
  1264		for i := b.N - 1; i >= 0; i-- {
  1265			altSetBit(z, z, i&512, 1)
  1266		}
  1267	}
  1268	
  1269	func BenchmarkBitsetNegOrig(b *testing.B) {
  1270		z := NewInt(-1)
  1271		altSetBit(z, z, 512, 0)
  1272		b.ResetTimer()
  1273		b.StartTimer()
  1274		for i := b.N - 1; i >= 0; i-- {
  1275			altSetBit(z, z, i&512, 0)
  1276		}
  1277	}
  1278	
  1279	func TestBitwise(t *testing.T) {
  1280		x := new(Int)
  1281		y := new(Int)
  1282		for _, test := range bitwiseTests {
  1283			x.SetString(test.x, 0)
  1284			y.SetString(test.y, 0)
  1285	
  1286			testBitFun(t, "and", (*Int).And, x, y, test.and)
  1287			testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
  1288			testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
  1289			testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
  1290			testBitFun(t, "or", (*Int).Or, x, y, test.or)
  1291			testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
  1292			testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
  1293			testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
  1294		}
  1295	}
  1296	
  1297	var notTests = []struct {
  1298		in  string
  1299		out string
  1300	}{
  1301		{"0", "-1"},
  1302		{"1", "-2"},
  1303		{"7", "-8"},
  1304		{"0", "-1"},
  1305		{"-81910", "81909"},
  1306		{
  1307			"298472983472983471903246121093472394872319615612417471234712061",
  1308			"-298472983472983471903246121093472394872319615612417471234712062",
  1309		},
  1310	}
  1311	
  1312	func TestNot(t *testing.T) {
  1313		in := new(Int)
  1314		out := new(Int)
  1315		expected := new(Int)
  1316		for i, test := range notTests {
  1317			in.SetString(test.in, 10)
  1318			expected.SetString(test.out, 10)
  1319			out = out.Not(in)
  1320			if out.Cmp(expected) != 0 {
  1321				t.Errorf("#%d: got %s want %s", i, out, expected)
  1322			}
  1323			out = out.Not(out)
  1324			if out.Cmp(in) != 0 {
  1325				t.Errorf("#%d: got %s want %s", i, out, in)
  1326			}
  1327		}
  1328	}
  1329	
  1330	var modInverseTests = []struct {
  1331		element string
  1332		prime   string
  1333	}{
  1334		{"1", "7"},
  1335		{"1", "13"},
  1336		{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
  1337	}
  1338	
  1339	func TestModInverse(t *testing.T) {
  1340		var element, prime Int
  1341		one := NewInt(1)
  1342		for i, test := range modInverseTests {
  1343			(&element).SetString(test.element, 10)
  1344			(&prime).SetString(test.prime, 10)
  1345			inverse := new(Int).ModInverse(&element, &prime)
  1346			inverse.Mul(inverse, &element)
  1347			inverse.Mod(inverse, &prime)
  1348			if inverse.Cmp(one) != 0 {
  1349				t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse)
  1350			}
  1351		}
  1352	}
  1353	
  1354	// used by TestIntGobEncoding and TestRatGobEncoding
  1355	var gobEncodingTests = []string{
  1356		"0",
  1357		"1",
  1358		"2",
  1359		"10",
  1360		"42",
  1361		"1234567890",
  1362		"298472983472983471903246121093472394872319615612417471234712061",
  1363	}
  1364	
  1365	func TestIntGobEncoding(t *testing.T) {
  1366		var medium bytes.Buffer
  1367		enc := gob.NewEncoder(&medium)
  1368		dec := gob.NewDecoder(&medium)
  1369		for i, test := range gobEncodingTests {
  1370			for j := 0; j < 2; j++ {
  1371				medium.Reset() // empty buffer for each test case (in case of failures)
  1372				stest := test
  1373				if j != 0 {
  1374					// negative numbers
  1375					stest = "-" + test
  1376				}
  1377				var tx Int
  1378				tx.SetString(stest, 10)
  1379				if err := enc.Encode(&tx); err != nil {
  1380					t.Errorf("#%d%c: encoding failed: %s", i, 'a'+j, err)
  1381				}
  1382				var rx Int
  1383				if err := dec.Decode(&rx); err != nil {
  1384					t.Errorf("#%d%c: decoding failed: %s", i, 'a'+j, err)
  1385				}
  1386				if rx.Cmp(&tx) != 0 {
  1387					t.Errorf("#%d%c: transmission failed: got %s want %s", i, 'a'+j, &rx, &tx)
  1388				}
  1389			}
  1390		}
  1391	}

release.r60.3. Except as noted, this content is licensed under a Creative Commons Attribution 3.0 License.