...
Run Format

Source file src/math/big/arith_test.go

Documentation: math/big

     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  	"fmt"
     9  	"internal/testenv"
    10  	"math/rand"
    11  	"strings"
    12  	"testing"
    13  )
    14  
    15  var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race")
    16  
    17  type funWW func(x, y, c Word) (z1, z0 Word)
    18  type argWW struct {
    19  	x, y, c, z1, z0 Word
    20  }
    21  
    22  var sumWW = []argWW{
    23  	{0, 0, 0, 0, 0},
    24  	{0, 1, 0, 0, 1},
    25  	{0, 0, 1, 0, 1},
    26  	{0, 1, 1, 0, 2},
    27  	{12345, 67890, 0, 0, 80235},
    28  	{12345, 67890, 1, 0, 80236},
    29  	{_M, 1, 0, 1, 0},
    30  	{_M, 0, 1, 1, 0},
    31  	{_M, 1, 1, 1, 1},
    32  	{_M, _M, 0, 1, _M - 1},
    33  	{_M, _M, 1, 1, _M},
    34  }
    35  
    36  func testFunWW(t *testing.T, msg string, f funWW, a argWW) {
    37  	z1, z0 := f(a.x, a.y, a.c)
    38  	if z1 != a.z1 || z0 != a.z0 {
    39  		t.Errorf("%s%+v\n\tgot z1:z0 = %#x:%#x; want %#x:%#x", msg, a, z1, z0, a.z1, a.z0)
    40  	}
    41  }
    42  
    43  func TestFunWW(t *testing.T) {
    44  	for _, a := range sumWW {
    45  		arg := a
    46  		testFunWW(t, "addWW_g", addWW_g, arg)
    47  
    48  		arg = argWW{a.y, a.x, a.c, a.z1, a.z0}
    49  		testFunWW(t, "addWW_g symmetric", addWW_g, arg)
    50  
    51  		arg = argWW{a.z0, a.x, a.c, a.z1, a.y}
    52  		testFunWW(t, "subWW_g", subWW_g, arg)
    53  
    54  		arg = argWW{a.z0, a.y, a.c, a.z1, a.x}
    55  		testFunWW(t, "subWW_g symmetric", subWW_g, arg)
    56  	}
    57  }
    58  
    59  type funVV func(z, x, y []Word) (c Word)
    60  type argVV struct {
    61  	z, x, y nat
    62  	c       Word
    63  }
    64  
    65  var sumVV = []argVV{
    66  	{},
    67  	{nat{0}, nat{0}, nat{0}, 0},
    68  	{nat{1}, nat{1}, nat{0}, 0},
    69  	{nat{0}, nat{_M}, nat{1}, 1},
    70  	{nat{80235}, nat{12345}, nat{67890}, 0},
    71  	{nat{_M - 1}, nat{_M}, nat{_M}, 1},
    72  	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
    73  	{nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
    74  	{nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
    75  }
    76  
    77  func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
    78  	z := make(nat, len(a.z))
    79  	c := f(z, a.x, a.y)
    80  	for i, zi := range z {
    81  		if zi != a.z[i] {
    82  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
    83  			break
    84  		}
    85  	}
    86  	if c != a.c {
    87  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
    88  	}
    89  }
    90  
    91  func TestFunVV(t *testing.T) {
    92  	for _, a := range sumVV {
    93  		arg := a
    94  		testFunVV(t, "addVV_g", addVV_g, arg)
    95  		testFunVV(t, "addVV", addVV, arg)
    96  
    97  		arg = argVV{a.z, a.y, a.x, a.c}
    98  		testFunVV(t, "addVV_g symmetric", addVV_g, arg)
    99  		testFunVV(t, "addVV symmetric", addVV, arg)
   100  
   101  		arg = argVV{a.x, a.z, a.y, a.c}
   102  		testFunVV(t, "subVV_g", subVV_g, arg)
   103  		testFunVV(t, "subVV", subVV, arg)
   104  
   105  		arg = argVV{a.y, a.z, a.x, a.c}
   106  		testFunVV(t, "subVV_g symmetric", subVV_g, arg)
   107  		testFunVV(t, "subVV symmetric", subVV, arg)
   108  	}
   109  }
   110  
   111  // Always the same seed for reproducible results.
   112  var rnd = rand.New(rand.NewSource(0))
   113  
   114  func rndW() Word {
   115  	return Word(rnd.Int63()<<1 | rnd.Int63n(2))
   116  }
   117  
   118  func rndV(n int) []Word {
   119  	v := make([]Word, n)
   120  	for i := range v {
   121  		v[i] = rndW()
   122  	}
   123  	return v
   124  }
   125  
   126  var benchSizes = []int{1, 2, 3, 4, 5, 1e1, 1e2, 1e3, 1e4, 1e5}
   127  
   128  func BenchmarkAddVV(b *testing.B) {
   129  	for _, n := range benchSizes {
   130  		if isRaceBuilder && n > 1e3 {
   131  			continue
   132  		}
   133  		x := rndV(n)
   134  		y := rndV(n)
   135  		z := make([]Word, n)
   136  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   137  			b.SetBytes(int64(n * _W))
   138  			for i := 0; i < b.N; i++ {
   139  				addVV(z, x, y)
   140  			}
   141  		})
   142  	}
   143  }
   144  
   145  func BenchmarkSubVV(b *testing.B) {
   146  	for _, n := range benchSizes {
   147  		if isRaceBuilder && n > 1e3 {
   148  			continue
   149  		}
   150  		x := rndV(n)
   151  		y := rndV(n)
   152  		z := make([]Word, n)
   153  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   154  			b.SetBytes(int64(n * _W))
   155  			for i := 0; i < b.N; i++ {
   156  				subVV(z, x, y)
   157  			}
   158  		})
   159  	}
   160  }
   161  
   162  type funVW func(z, x []Word, y Word) (c Word)
   163  type argVW struct {
   164  	z, x nat
   165  	y    Word
   166  	c    Word
   167  }
   168  
   169  var sumVW = []argVW{
   170  	{},
   171  	{nil, nil, 2, 2},
   172  	{nat{0}, nat{0}, 0, 0},
   173  	{nat{1}, nat{0}, 1, 0},
   174  	{nat{1}, nat{1}, 0, 0},
   175  	{nat{0}, nat{_M}, 1, 1},
   176  	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
   177  	{nat{585}, nat{314}, 271, 0},
   178  }
   179  
   180  var lshVW = []argVW{
   181  	{},
   182  	{nat{0}, nat{0}, 0, 0},
   183  	{nat{0}, nat{0}, 1, 0},
   184  	{nat{0}, nat{0}, 20, 0},
   185  
   186  	{nat{_M}, nat{_M}, 0, 0},
   187  	{nat{_M << 1 & _M}, nat{_M}, 1, 1},
   188  	{nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
   189  
   190  	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
   191  	{nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
   192  	{nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
   193  }
   194  
   195  var rshVW = []argVW{
   196  	{},
   197  	{nat{0}, nat{0}, 0, 0},
   198  	{nat{0}, nat{0}, 1, 0},
   199  	{nat{0}, nat{0}, 20, 0},
   200  
   201  	{nat{_M}, nat{_M}, 0, 0},
   202  	{nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
   203  	{nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
   204  
   205  	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
   206  	{nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
   207  	{nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
   208  }
   209  
   210  func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
   211  	z := make(nat, len(a.z))
   212  	c := f(z, a.x, a.y)
   213  	for i, zi := range z {
   214  		if zi != a.z[i] {
   215  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   216  			break
   217  		}
   218  	}
   219  	if c != a.c {
   220  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
   221  	}
   222  }
   223  
   224  func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
   225  	return func(z, x []Word, s Word) (c Word) {
   226  		return f(z, x, uint(s))
   227  	}
   228  }
   229  
   230  func TestFunVW(t *testing.T) {
   231  	for _, a := range sumVW {
   232  		arg := a
   233  		testFunVW(t, "addVW_g", addVW_g, arg)
   234  		testFunVW(t, "addVW", addVW, arg)
   235  
   236  		arg = argVW{a.x, a.z, a.y, a.c}
   237  		testFunVW(t, "subVW_g", subVW_g, arg)
   238  		testFunVW(t, "subVW", subVW, arg)
   239  	}
   240  
   241  	shlVW_g := makeFunVW(shlVU_g)
   242  	shlVW := makeFunVW(shlVU)
   243  	for _, a := range lshVW {
   244  		arg := a
   245  		testFunVW(t, "shlVU_g", shlVW_g, arg)
   246  		testFunVW(t, "shlVU", shlVW, arg)
   247  	}
   248  
   249  	shrVW_g := makeFunVW(shrVU_g)
   250  	shrVW := makeFunVW(shrVU)
   251  	for _, a := range rshVW {
   252  		arg := a
   253  		testFunVW(t, "shrVU_g", shrVW_g, arg)
   254  		testFunVW(t, "shrVU", shrVW, arg)
   255  	}
   256  }
   257  
   258  func BenchmarkAddVW(b *testing.B) {
   259  	for _, n := range benchSizes {
   260  		if isRaceBuilder && n > 1e3 {
   261  			continue
   262  		}
   263  		x := rndV(n)
   264  		y := rndW()
   265  		z := make([]Word, n)
   266  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   267  			b.SetBytes(int64(n * _S))
   268  			for i := 0; i < b.N; i++ {
   269  				addVW(z, x, y)
   270  			}
   271  		})
   272  	}
   273  }
   274  
   275  func BenchmarkSubVW(b *testing.B) {
   276  	for _, n := range benchSizes {
   277  		if isRaceBuilder && n > 1e3 {
   278  			continue
   279  		}
   280  		x := rndV(n)
   281  		y := rndW()
   282  		z := make([]Word, n)
   283  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   284  			b.SetBytes(int64(n * _S))
   285  			for i := 0; i < b.N; i++ {
   286  				subVW(z, x, y)
   287  			}
   288  		})
   289  	}
   290  }
   291  
   292  type funVWW func(z, x []Word, y, r Word) (c Word)
   293  type argVWW struct {
   294  	z, x nat
   295  	y, r Word
   296  	c    Word
   297  }
   298  
   299  var prodVWW = []argVWW{
   300  	{},
   301  	{nat{0}, nat{0}, 0, 0, 0},
   302  	{nat{991}, nat{0}, 0, 991, 0},
   303  	{nat{0}, nat{_M}, 0, 0, 0},
   304  	{nat{991}, nat{_M}, 0, 991, 0},
   305  	{nat{0}, nat{0}, _M, 0, 0},
   306  	{nat{991}, nat{0}, _M, 991, 0},
   307  	{nat{1}, nat{1}, 1, 0, 0},
   308  	{nat{992}, nat{1}, 1, 991, 0},
   309  	{nat{22793}, nat{991}, 23, 0, 0},
   310  	{nat{22800}, nat{991}, 23, 7, 0},
   311  	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
   312  	{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
   313  	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
   314  	{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
   315  	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
   316  	{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
   317  	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
   318  	{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
   319  	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
   320  	{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   321  	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
   322  	{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   323  }
   324  
   325  func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
   326  	z := make(nat, len(a.z))
   327  	c := f(z, a.x, a.y, a.r)
   328  	for i, zi := range z {
   329  		if zi != a.z[i] {
   330  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   331  			break
   332  		}
   333  	}
   334  	if c != a.c {
   335  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
   336  	}
   337  }
   338  
   339  // TODO(gri) mulAddVWW and divWVW are symmetric operations but
   340  //           their signature is not symmetric. Try to unify.
   341  
   342  type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
   343  type argWVW struct {
   344  	z  nat
   345  	xn Word
   346  	x  nat
   347  	y  Word
   348  	r  Word
   349  }
   350  
   351  func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
   352  	z := make(nat, len(a.z))
   353  	r := f(z, a.xn, a.x, a.y)
   354  	for i, zi := range z {
   355  		if zi != a.z[i] {
   356  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   357  			break
   358  		}
   359  	}
   360  	if r != a.r {
   361  		t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
   362  	}
   363  }
   364  
   365  func TestFunVWW(t *testing.T) {
   366  	for _, a := range prodVWW {
   367  		arg := a
   368  		testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
   369  		testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
   370  
   371  		if a.y != 0 && a.r < a.y {
   372  			arg := argWVW{a.x, a.c, a.z, a.y, a.r}
   373  			testFunWVW(t, "divWVW_g", divWVW_g, arg)
   374  			testFunWVW(t, "divWVW", divWVW, arg)
   375  		}
   376  	}
   377  }
   378  
   379  var mulWWTests = []struct {
   380  	x, y Word
   381  	q, r Word
   382  }{
   383  	{_M, _M, _M - 1, 1},
   384  	// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
   385  }
   386  
   387  func TestMulWW(t *testing.T) {
   388  	for i, test := range mulWWTests {
   389  		q, r := mulWW_g(test.x, test.y)
   390  		if q != test.q || r != test.r {
   391  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   392  		}
   393  	}
   394  }
   395  
   396  var mulAddWWWTests = []struct {
   397  	x, y, c Word
   398  	q, r    Word
   399  }{
   400  	// TODO(agl): These will only work on 64-bit platforms.
   401  	// {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
   402  	// {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
   403  	{_M, _M, 0, _M - 1, 1},
   404  	{_M, _M, _M, _M, 0},
   405  }
   406  
   407  func TestMulAddWWW(t *testing.T) {
   408  	for i, test := range mulAddWWWTests {
   409  		q, r := mulAddWWW_g(test.x, test.y, test.c)
   410  		if q != test.q || r != test.r {
   411  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   412  		}
   413  	}
   414  }
   415  
   416  func BenchmarkAddMulVVW(b *testing.B) {
   417  	for _, n := range benchSizes {
   418  		if isRaceBuilder && n > 1e3 {
   419  			continue
   420  		}
   421  		x := rndV(n)
   422  		y := rndW()
   423  		z := make([]Word, n)
   424  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   425  			b.SetBytes(int64(n * _W))
   426  			for i := 0; i < b.N; i++ {
   427  				addMulVVW(z, x, y)
   428  			}
   429  		})
   430  	}
   431  }
   432  

View as plain text