# Source file src/math/big/arith.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  // This file provides Go implementations of elementary multi-precision
6  // arithmetic operations on word vectors. These have the suffix _g.
7  // These are needed for platforms without assembly implementations of these routines.
8  // This file also contains elementary operations that can be implemented
9  // sufficiently efficiently in Go.
10
11  package big
12
13  import "math/bits"
14
15  // A Word represents a single digit of a multi-precision unsigned integer.
16  type Word uint
17
18  const (
19  	_S = _W / 8 // word size in bytes
20
21  	_W = bits.UintSize // word size in bits
22  	_B = 1 << _W       // digit base
23  	_M = _B - 1        // digit mask
24  )
25
26  // Many of the loops in this file are of the form
27  //   for i := 0; i < len(z) && i < len(x) && i < len(y); i++
28  // i < len(z) is the real condition.
29  // However, checking i < len(x) && i < len(y) as well is faster than
30  // having the compiler do a bounds check in the body of the loop;
31  // remarkably it is even faster than hoisting the bounds check
32  // out of the loop, by doing something like
33  //   _, _ = x[len(z)-1], y[len(z)-1]
34  // There are other ways to hoist the bounds check out of the loop,
35  // but the compiler's BCE isn't powerful enough for them (yet?).
36  // See the discussion in CL 164966.
37
38  // ----------------------------------------------------------------------------
39  // Elementary operations on words
40  //
41  // These operations are used by the vector operations below.
42
43  // z1<<_W + z0 = x*y
44  func mulWW_g(x, y Word) (z1, z0 Word) {
45  	hi, lo := bits.Mul(uint(x), uint(y))
46  	return Word(hi), Word(lo)
47  }
48
49  // z1<<_W + z0 = x*y + c
50  func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
51  	hi, lo := bits.Mul(uint(x), uint(y))
52  	var cc uint
53  	lo, cc = bits.Add(lo, uint(c), 0)
54  	return Word(hi + cc), Word(lo)
55  }
56
57  // nlz returns the number of leading zeros in x.
58  // Wraps bits.LeadingZeros call for convenience.
59  func nlz(x Word) uint {
61  }
62
63  // q = (u1<<_W + u0 - r)/v
64  func divWW_g(u1, u0, v Word) (q, r Word) {
65  	qq, rr := bits.Div(uint(u1), uint(u0), uint(v))
66  	return Word(qq), Word(rr)
67  }
68
69  // The resulting carry c is either 0 or 1.
70  func addVV_g(z, x, y []Word) (c Word) {
71  	// The comment near the top of this file discusses this for loop condition.
72  	for i := 0; i < len(z) && i < len(x) && i < len(y); i++ {
73  		zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
74  		z[i] = Word(zi)
75  		c = Word(cc)
76  	}
77  	return
78  }
79
80  // The resulting carry c is either 0 or 1.
81  func subVV_g(z, x, y []Word) (c Word) {
82  	// The comment near the top of this file discusses this for loop condition.
83  	for i := 0; i < len(z) && i < len(x) && i < len(y); i++ {
84  		zi, cc := bits.Sub(uint(x[i]), uint(y[i]), uint(c))
85  		z[i] = Word(zi)
86  		c = Word(cc)
87  	}
88  	return
89  }
90
91  // The resulting carry c is either 0 or 1.
92  func addVW_g(z, x []Word, y Word) (c Word) {
93  	c = y
94  	// The comment near the top of this file discusses this for loop condition.
95  	for i := 0; i < len(z) && i < len(x); i++ {
96  		zi, cc := bits.Add(uint(x[i]), uint(c), 0)
97  		z[i] = Word(zi)
98  		c = Word(cc)
99  	}
100  	return
101  }
102
103  // addVWlarge is addVW, but intended for large z.
104  // The only difference is that we check on every iteration
105  // whether we are done with carries,
106  // and if so, switch to a much faster copy instead.
107  // This is only a good idea for large z,
108  // because the overhead of the check and the function call
109  // outweigh the benefits when z is small.
110  func addVWlarge(z, x []Word, y Word) (c Word) {
111  	c = y
112  	// The comment near the top of this file discusses this for loop condition.
113  	for i := 0; i < len(z) && i < len(x); i++ {
114  		if c == 0 {
115  			copy(z[i:], x[i:])
116  			return
117  		}
118  		zi, cc := bits.Add(uint(x[i]), uint(c), 0)
119  		z[i] = Word(zi)
120  		c = Word(cc)
121  	}
122  	return
123  }
124
125  func subVW_g(z, x []Word, y Word) (c Word) {
126  	c = y
127  	// The comment near the top of this file discusses this for loop condition.
128  	for i := 0; i < len(z) && i < len(x); i++ {
129  		zi, cc := bits.Sub(uint(x[i]), uint(c), 0)
130  		z[i] = Word(zi)
131  		c = Word(cc)
132  	}
133  	return
134  }
135
136  // subVWlarge is to subVW as addVWlarge is to addVW.
137  func subVWlarge(z, x []Word, y Word) (c Word) {
138  	c = y
139  	// The comment near the top of this file discusses this for loop condition.
140  	for i := 0; i < len(z) && i < len(x); i++ {
141  		if c == 0 {
142  			copy(z[i:], x[i:])
143  			return
144  		}
145  		zi, cc := bits.Sub(uint(x[i]), uint(c), 0)
146  		z[i] = Word(zi)
147  		c = Word(cc)
148  	}
149  	return
150  }
151
152  func shlVU_g(z, x []Word, s uint) (c Word) {
153  	if s == 0 {
154  		copy(z, x)
155  		return
156  	}
157  	if len(z) == 0 {
158  		return
159  	}
160  	s &= _W - 1 // hint to the compiler that shifts by s don't need guard code
161  	ŝ := _W - s
162  	ŝ &= _W - 1 // ditto
163  	c = x[len(z)-1] >> ŝ
164  	for i := len(z) - 1; i > 0; i-- {
165  		z[i] = x[i]<<s | x[i-1]>>ŝ
166  	}
167  	z = x << s
168  	return
169  }
170
171  func shrVU_g(z, x []Word, s uint) (c Word) {
172  	if s == 0 {
173  		copy(z, x)
174  		return
175  	}
176  	if len(z) == 0 {
177  		return
178  	}
179  	s &= _W - 1 // hint to the compiler that shifts by s don't need guard code
180  	ŝ := _W - s
181  	ŝ &= _W - 1 // ditto
182  	c = x << ŝ
183  	for i := 0; i < len(z)-1; i++ {
184  		z[i] = x[i]>>s | x[i+1]<<ŝ
185  	}
186  	z[len(z)-1] = x[len(z)-1] >> s
187  	return
188  }
189
190  func mulAddVWW_g(z, x []Word, y, r Word) (c Word) {
191  	c = r
192  	// The comment near the top of this file discusses this for loop condition.
193  	for i := 0; i < len(z) && i < len(x); i++ {
194  		c, z[i] = mulAddWWW_g(x[i], y, c)
195  	}
196  	return
197  }
198
199  func addMulVVW_g(z, x []Word, y Word) (c Word) {
200  	// The comment near the top of this file discusses this for loop condition.
201  	for i := 0; i < len(z) && i < len(x); i++ {
202  		z1, z0 := mulAddWWW_g(x[i], y, z[i])
203  		lo, cc := bits.Add(uint(z0), uint(c), 0)
204  		c, z[i] = Word(cc), Word(lo)
205  		c += z1
206  	}
207  	return
208  }
209
210  func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word) {
211  	r = xn
212  	for i := len(z) - 1; i >= 0; i-- {
213  		z[i], r = divWW_g(r, x[i], y)
214  	}
215  	return
216  }
217
```

View as plain text