]>
Commit | Line | Data |
---|---|---|
7a938933 ILT |
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 implements signed multi-precision integers. | |
6 | ||
7 | package big | |
8 | ||
9 | import ( | |
2fd401c8 | 10 | "errors" |
7a938933 | 11 | "fmt" |
adb0401d | 12 | "io" |
9c63abc9 | 13 | "math/rand" |
adb0401d | 14 | "strings" |
7a938933 ILT |
15 | ) |
16 | ||
17 | // An Int represents a signed multi-precision integer. | |
18 | // The zero value for an Int represents the value 0. | |
19 | type Int struct { | |
20 | neg bool // sign | |
21 | abs nat // absolute value of the integer | |
22 | } | |
23 | ||
7a938933 ILT |
24 | var intOne = &Int{false, natOne} |
25 | ||
7a938933 ILT |
26 | // Sign returns: |
27 | // | |
28 | // -1 if x < 0 | |
29 | // 0 if x == 0 | |
30 | // +1 if x > 0 | |
31 | // | |
32 | func (x *Int) Sign() int { | |
33 | if len(x.abs) == 0 { | |
34 | return 0 | |
35 | } | |
36 | if x.neg { | |
37 | return -1 | |
38 | } | |
39 | return 1 | |
40 | } | |
41 | ||
7a938933 ILT |
42 | // SetInt64 sets z to x and returns z. |
43 | func (z *Int) SetInt64(x int64) *Int { | |
44 | neg := false | |
45 | if x < 0 { | |
46 | neg = true | |
47 | x = -x | |
48 | } | |
49 | z.abs = z.abs.setUint64(uint64(x)) | |
50 | z.neg = neg | |
51 | return z | |
52 | } | |
53 | ||
409a5e7e ILT |
54 | // SetUint64 sets z to x and returns z. |
55 | func (z *Int) SetUint64(x uint64) *Int { | |
be47d6ec | 56 | z.abs = z.abs.setUint64(x) |
409a5e7e ILT |
57 | z.neg = false |
58 | return z | |
59 | } | |
60 | ||
7a938933 ILT |
61 | // NewInt allocates and returns a new Int set to x. |
62 | func NewInt(x int64) *Int { | |
63 | return new(Int).SetInt64(x) | |
64 | } | |
65 | ||
7a938933 ILT |
66 | // Set sets z to x and returns z. |
67 | func (z *Int) Set(x *Int) *Int { | |
b740cb63 ILT |
68 | if z != x { |
69 | z.abs = z.abs.set(x.abs) | |
70 | z.neg = x.neg | |
71 | } | |
7a938933 ILT |
72 | return z |
73 | } | |
74 | ||
94252f4b ILT |
75 | // Bits provides raw (unchecked but fast) access to x by returning its |
76 | // absolute value as a little-endian Word slice. The result and x share | |
77 | // the same underlying array. | |
78 | // Bits is intended to support implementation of missing low-level Int | |
79 | // functionality outside this package; it should be avoided otherwise. | |
80 | func (x *Int) Bits() []Word { | |
81 | return x.abs | |
82 | } | |
83 | ||
84 | // SetBits provides raw (unchecked but fast) access to z by setting its | |
85 | // value to abs, interpreted as a little-endian Word slice, and returning | |
86 | // z. The result and abs share the same underlying array. | |
87 | // SetBits is intended to support implementation of missing low-level Int | |
88 | // functionality outside this package; it should be avoided otherwise. | |
89 | func (z *Int) SetBits(abs []Word) *Int { | |
90 | z.abs = nat(abs).norm() | |
91 | z.neg = false | |
92 | return z | |
93 | } | |
94 | ||
7a938933 ILT |
95 | // Abs sets z to |x| (the absolute value of x) and returns z. |
96 | func (z *Int) Abs(x *Int) *Int { | |
b740cb63 | 97 | z.Set(x) |
7a938933 ILT |
98 | z.neg = false |
99 | return z | |
100 | } | |
101 | ||
7a938933 ILT |
102 | // Neg sets z to -x and returns z. |
103 | func (z *Int) Neg(x *Int) *Int { | |
b740cb63 ILT |
104 | z.Set(x) |
105 | z.neg = len(z.abs) > 0 && !z.neg // 0 has no sign | |
7a938933 ILT |
106 | return z |
107 | } | |
108 | ||
7a938933 ILT |
109 | // Add sets z to the sum x+y and returns z. |
110 | func (z *Int) Add(x, y *Int) *Int { | |
111 | neg := x.neg | |
112 | if x.neg == y.neg { | |
113 | // x + y == x + y | |
114 | // (-x) + (-y) == -(x + y) | |
115 | z.abs = z.abs.add(x.abs, y.abs) | |
116 | } else { | |
117 | // x + (-y) == x - y == -(y - x) | |
118 | // (-x) + y == y - x == -(x - y) | |
119 | if x.abs.cmp(y.abs) >= 0 { | |
120 | z.abs = z.abs.sub(x.abs, y.abs) | |
121 | } else { | |
122 | neg = !neg | |
123 | z.abs = z.abs.sub(y.abs, x.abs) | |
124 | } | |
125 | } | |
126 | z.neg = len(z.abs) > 0 && neg // 0 has no sign | |
127 | return z | |
128 | } | |
129 | ||
7a938933 ILT |
130 | // Sub sets z to the difference x-y and returns z. |
131 | func (z *Int) Sub(x, y *Int) *Int { | |
132 | neg := x.neg | |
133 | if x.neg != y.neg { | |
134 | // x - (-y) == x + y | |
135 | // (-x) - y == -(x + y) | |
136 | z.abs = z.abs.add(x.abs, y.abs) | |
137 | } else { | |
138 | // x - y == x - y == -(y - x) | |
139 | // (-x) - (-y) == y - x == -(x - y) | |
140 | if x.abs.cmp(y.abs) >= 0 { | |
141 | z.abs = z.abs.sub(x.abs, y.abs) | |
142 | } else { | |
143 | neg = !neg | |
144 | z.abs = z.abs.sub(y.abs, x.abs) | |
145 | } | |
146 | } | |
147 | z.neg = len(z.abs) > 0 && neg // 0 has no sign | |
148 | return z | |
149 | } | |
150 | ||
7a938933 ILT |
151 | // Mul sets z to the product x*y and returns z. |
152 | func (z *Int) Mul(x, y *Int) *Int { | |
153 | // x * y == x * y | |
154 | // x * (-y) == -(x * y) | |
155 | // (-x) * y == -(x * y) | |
156 | // (-x) * (-y) == x * y | |
157 | z.abs = z.abs.mul(x.abs, y.abs) | |
158 | z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign | |
159 | return z | |
160 | } | |
161 | ||
7a938933 ILT |
162 | // MulRange sets z to the product of all integers |
163 | // in the range [a, b] inclusively and returns z. | |
164 | // If a > b (empty range), the result is 1. | |
165 | func (z *Int) MulRange(a, b int64) *Int { | |
166 | switch { | |
167 | case a > b: | |
168 | return z.SetInt64(1) // empty range | |
169 | case a <= 0 && b >= 0: | |
170 | return z.SetInt64(0) // range includes 0 | |
171 | } | |
172 | // a <= b && (b < 0 || a > 0) | |
173 | ||
174 | neg := false | |
175 | if a < 0 { | |
176 | neg = (b-a)&1 == 0 | |
177 | a, b = -b, -a | |
178 | } | |
179 | ||
180 | z.abs = z.abs.mulRange(uint64(a), uint64(b)) | |
181 | z.neg = neg | |
182 | return z | |
183 | } | |
184 | ||
7a938933 ILT |
185 | // Binomial sets z to the binomial coefficient of (n, k) and returns z. |
186 | func (z *Int) Binomial(n, k int64) *Int { | |
187 | var a, b Int | |
188 | a.MulRange(n-k+1, n) | |
189 | b.MulRange(1, k) | |
190 | return z.Quo(&a, &b) | |
191 | } | |
192 | ||
7a938933 ILT |
193 | // Quo sets z to the quotient x/y for y != 0 and returns z. |
194 | // If y == 0, a division-by-zero run-time panic occurs. | |
d8f41257 | 195 | // Quo implements truncated division (like Go); see QuoRem for more details. |
7a938933 ILT |
196 | func (z *Int) Quo(x, y *Int) *Int { |
197 | z.abs, _ = z.abs.div(nil, x.abs, y.abs) | |
198 | z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign | |
199 | return z | |
200 | } | |
201 | ||
7a938933 ILT |
202 | // Rem sets z to the remainder x%y for y != 0 and returns z. |
203 | // If y == 0, a division-by-zero run-time panic occurs. | |
d8f41257 | 204 | // Rem implements truncated modulus (like Go); see QuoRem for more details. |
7a938933 | 205 | func (z *Int) Rem(x, y *Int) *Int { |
ab61e9c4 | 206 | _, z.abs = nat(nil).div(z.abs, x.abs, y.abs) |
7a938933 ILT |
207 | z.neg = len(z.abs) > 0 && x.neg // 0 has no sign |
208 | return z | |
209 | } | |
210 | ||
7a938933 ILT |
211 | // QuoRem sets z to the quotient x/y and r to the remainder x%y |
212 | // and returns the pair (z, r) for y != 0. | |
213 | // If y == 0, a division-by-zero run-time panic occurs. | |
214 | // | |
215 | // QuoRem implements T-division and modulus (like Go): | |
216 | // | |
217 | // q = x/y with the result truncated to zero | |
218 | // r = x - y*q | |
219 | // | |
220 | // (See Daan Leijen, ``Division and Modulus for Computer Scientists''.) | |
94252f4b | 221 | // See DivMod for Euclidean division and modulus (unlike Go). |
7a938933 ILT |
222 | // |
223 | func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) { | |
224 | z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs) | |
225 | z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg // 0 has no sign | |
226 | return z, r | |
227 | } | |
228 | ||
7a938933 ILT |
229 | // Div sets z to the quotient x/y for y != 0 and returns z. |
230 | // If y == 0, a division-by-zero run-time panic occurs. | |
d8f41257 | 231 | // Div implements Euclidean division (unlike Go); see DivMod for more details. |
7a938933 ILT |
232 | func (z *Int) Div(x, y *Int) *Int { |
233 | y_neg := y.neg // z may be an alias for y | |
234 | var r Int | |
235 | z.QuoRem(x, y, &r) | |
236 | if r.neg { | |
237 | if y_neg { | |
238 | z.Add(z, intOne) | |
239 | } else { | |
240 | z.Sub(z, intOne) | |
241 | } | |
242 | } | |
243 | return z | |
244 | } | |
245 | ||
7a938933 ILT |
246 | // Mod sets z to the modulus x%y for y != 0 and returns z. |
247 | // If y == 0, a division-by-zero run-time panic occurs. | |
d8f41257 | 248 | // Mod implements Euclidean modulus (unlike Go); see DivMod for more details. |
7a938933 ILT |
249 | func (z *Int) Mod(x, y *Int) *Int { |
250 | y0 := y // save y | |
251 | if z == y || alias(z.abs, y.abs) { | |
252 | y0 = new(Int).Set(y) | |
253 | } | |
254 | var q Int | |
255 | q.QuoRem(x, y, z) | |
256 | if z.neg { | |
257 | if y0.neg { | |
258 | z.Sub(z, y0) | |
259 | } else { | |
260 | z.Add(z, y0) | |
261 | } | |
262 | } | |
263 | return z | |
264 | } | |
265 | ||
7a938933 ILT |
266 | // DivMod sets z to the quotient x div y and m to the modulus x mod y |
267 | // and returns the pair (z, m) for y != 0. | |
268 | // If y == 0, a division-by-zero run-time panic occurs. | |
269 | // | |
270 | // DivMod implements Euclidean division and modulus (unlike Go): | |
271 | // | |
272 | // q = x div y such that | |
273 | // m = x - y*q with 0 <= m < |q| | |
274 | // | |
275 | // (See Raymond T. Boute, ``The Euclidean definition of the functions | |
276 | // div and mod''. ACM Transactions on Programming Languages and | |
277 | // Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992. | |
278 | // ACM press.) | |
94252f4b | 279 | // See QuoRem for T-division and modulus (like Go). |
7a938933 ILT |
280 | // |
281 | func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) { | |
282 | y0 := y // save y | |
283 | if z == y || alias(z.abs, y.abs) { | |
284 | y0 = new(Int).Set(y) | |
285 | } | |
286 | z.QuoRem(x, y, m) | |
287 | if m.neg { | |
288 | if y0.neg { | |
289 | z.Add(z, intOne) | |
290 | m.Sub(m, y0) | |
291 | } else { | |
292 | z.Sub(z, intOne) | |
293 | m.Add(m, y0) | |
294 | } | |
295 | } | |
296 | return z, m | |
297 | } | |
298 | ||
7a938933 ILT |
299 | // Cmp compares x and y and returns: |
300 | // | |
301 | // -1 if x < y | |
302 | // 0 if x == y | |
303 | // +1 if x > y | |
304 | // | |
305 | func (x *Int) Cmp(y *Int) (r int) { | |
306 | // x cmp y == x cmp y | |
307 | // x cmp (-y) == x | |
308 | // (-x) cmp y == y | |
309 | // (-x) cmp (-y) == -(x cmp y) | |
310 | switch { | |
311 | case x.neg == y.neg: | |
312 | r = x.abs.cmp(y.abs) | |
313 | if x.neg { | |
314 | r = -r | |
315 | } | |
316 | case x.neg: | |
317 | r = -1 | |
318 | default: | |
319 | r = 1 | |
320 | } | |
321 | return | |
322 | } | |
323 | ||
7a938933 | 324 | func (x *Int) String() string { |
adb0401d ILT |
325 | switch { |
326 | case x == nil: | |
327 | return "<nil>" | |
328 | case x.neg: | |
329 | return "-" + x.abs.decimalString() | |
7a938933 | 330 | } |
adb0401d | 331 | return x.abs.decimalString() |
7a938933 ILT |
332 | } |
333 | ||
506cf9aa | 334 | func charset(ch rune) string { |
7a938933 ILT |
335 | switch ch { |
336 | case 'b': | |
adb0401d | 337 | return lowercaseDigits[0:2] |
7a938933 | 338 | case 'o': |
adb0401d ILT |
339 | return lowercaseDigits[0:8] |
340 | case 'd', 's', 'v': | |
341 | return lowercaseDigits[0:10] | |
7a938933 | 342 | case 'x': |
adb0401d ILT |
343 | return lowercaseDigits[0:16] |
344 | case 'X': | |
345 | return uppercaseDigits[0:16] | |
7a938933 | 346 | } |
adb0401d | 347 | return "" // unknown format |
7a938933 ILT |
348 | } |
349 | ||
adb0401d ILT |
350 | // write count copies of text to s |
351 | func writeMultiple(s fmt.State, text string, count int) { | |
352 | if len(text) > 0 { | |
353 | b := []byte(text) | |
354 | for ; count > 0; count-- { | |
355 | s.Write(b) | |
356 | } | |
357 | } | |
358 | } | |
7a938933 ILT |
359 | |
360 | // Format is a support routine for fmt.Formatter. It accepts | |
adb0401d ILT |
361 | // the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x' |
362 | // (lowercase hexadecimal), and 'X' (uppercase hexadecimal). | |
363 | // Also supported are the full suite of package fmt's format | |
364 | // verbs for integral types, including '+', '-', and ' ' | |
365 | // for sign control, '#' for leading zero in octal and for | |
366 | // hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X" | |
367 | // respectively, specification of minimum digits precision, | |
368 | // output field width, space or zero padding, and left or | |
369 | // right justification. | |
7a938933 | 370 | // |
506cf9aa | 371 | func (x *Int) Format(s fmt.State, ch rune) { |
adb0401d ILT |
372 | cs := charset(ch) |
373 | ||
374 | // special cases | |
375 | switch { | |
376 | case cs == "": | |
377 | // unknown format | |
378 | fmt.Fprintf(s, "%%!%c(big.Int=%s)", ch, x.String()) | |
379 | return | |
380 | case x == nil: | |
9ff56c95 ILT |
381 | fmt.Fprint(s, "<nil>") |
382 | return | |
383 | } | |
adb0401d ILT |
384 | |
385 | // determine sign character | |
386 | sign := "" | |
387 | switch { | |
388 | case x.neg: | |
389 | sign = "-" | |
390 | case s.Flag('+'): // supersedes ' ' when both specified | |
391 | sign = "+" | |
392 | case s.Flag(' '): | |
393 | sign = " " | |
394 | } | |
395 | ||
396 | // determine prefix characters for indicating output base | |
397 | prefix := "" | |
398 | if s.Flag('#') { | |
399 | switch ch { | |
400 | case 'o': // octal | |
401 | prefix = "0" | |
402 | case 'x': // hexadecimal | |
403 | prefix = "0x" | |
404 | case 'X': | |
405 | prefix = "0X" | |
406 | } | |
407 | } | |
408 | ||
409 | // determine digits with base set by len(cs) and digit characters from cs | |
410 | digits := x.abs.string(cs) | |
411 | ||
412 | // number of characters for the three classes of number padding | |
413 | var left int // space characters to left of digits for right justification ("%8d") | |
414 | var zeroes int // zero characters (actually cs[0]) as left-most digits ("%.8d") | |
415 | var right int // space characters to right of digits for left justification ("%-8d") | |
416 | ||
417 | // determine number padding from precision: the least number of digits to output | |
418 | precision, precisionSet := s.Precision() | |
419 | if precisionSet { | |
420 | switch { | |
421 | case len(digits) < precision: | |
fabcaa8d | 422 | zeroes = precision - len(digits) // count of zero padding |
adb0401d ILT |
423 | case digits == "0" && precision == 0: |
424 | return // print nothing if zero value (x == 0) and zero precision ("." or ".0") | |
425 | } | |
426 | } | |
427 | ||
428 | // determine field pad from width: the least number of characters to output | |
429 | length := len(sign) + len(prefix) + zeroes + len(digits) | |
430 | if width, widthSet := s.Width(); widthSet && length < width { // pad as specified | |
431 | switch d := width - length; { | |
432 | case s.Flag('-'): | |
433 | // pad on the right with spaces; supersedes '0' when both specified | |
434 | right = d | |
435 | case s.Flag('0') && !precisionSet: | |
436 | // pad with zeroes unless precision also specified | |
437 | zeroes = d | |
438 | default: | |
439 | // pad on the left with spaces | |
440 | left = d | |
441 | } | |
7a938933 | 442 | } |
adb0401d ILT |
443 | |
444 | // print number as [left pad][sign][prefix][zero pad][digits][right pad] | |
445 | writeMultiple(s, " ", left) | |
446 | writeMultiple(s, sign, 1) | |
447 | writeMultiple(s, prefix, 1) | |
448 | writeMultiple(s, "0", zeroes) | |
449 | writeMultiple(s, digits, 1) | |
450 | writeMultiple(s, " ", right) | |
7a938933 ILT |
451 | } |
452 | ||
adb0401d ILT |
453 | // scan sets z to the integer value corresponding to the longest possible prefix |
454 | // read from r representing a signed integer number in a given conversion base. | |
455 | // It returns z, the actual conversion base used, and an error, if any. In the | |
b740cb63 ILT |
456 | // error case, the value of z is undefined but the returned value is nil. The |
457 | // syntax follows the syntax of integer literals in Go. | |
adb0401d ILT |
458 | // |
459 | // The base argument must be 0 or a value from 2 through MaxBase. If the base | |
460 | // is 0, the string prefix determines the actual conversion base. A prefix of | |
461 | // ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a | |
462 | // ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10. | |
463 | // | |
2fd401c8 | 464 | func (z *Int) scan(r io.RuneScanner, base int) (*Int, int, error) { |
adb0401d ILT |
465 | // determine sign |
466 | ch, _, err := r.ReadRune() | |
467 | if err != nil { | |
b740cb63 | 468 | return nil, 0, err |
adb0401d ILT |
469 | } |
470 | neg := false | |
471 | switch ch { | |
472 | case '-': | |
473 | neg = true | |
474 | case '+': // nothing to do | |
475 | default: | |
476 | r.UnreadRune() | |
477 | } | |
7a938933 | 478 | |
adb0401d ILT |
479 | // determine mantissa |
480 | z.abs, base, err = z.abs.scan(r, base) | |
481 | if err != nil { | |
b740cb63 | 482 | return nil, base, err |
adb0401d ILT |
483 | } |
484 | z.neg = len(z.abs) > 0 && neg // 0 has no sign | |
485 | ||
486 | return z, base, nil | |
487 | } | |
488 | ||
489 | // Scan is a support routine for fmt.Scanner; it sets z to the value of | |
490 | // the scanned number. It accepts the formats 'b' (binary), 'o' (octal), | |
491 | // 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal). | |
2fd401c8 | 492 | func (z *Int) Scan(s fmt.ScanState, ch rune) error { |
adb0401d ILT |
493 | s.SkipSpace() // skip leading space characters |
494 | base := 0 | |
495 | switch ch { | |
496 | case 'b': | |
497 | base = 2 | |
498 | case 'o': | |
499 | base = 8 | |
500 | case 'd': | |
501 | base = 10 | |
502 | case 'x', 'X': | |
503 | base = 16 | |
504 | case 's', 'v': | |
505 | // let scan determine the base | |
506 | default: | |
2fd401c8 | 507 | return errors.New("Int.Scan: invalid verb") |
adb0401d ILT |
508 | } |
509 | _, _, err := z.scan(s, base) | |
510 | return err | |
511 | } | |
512 | ||
f8d9fa9e ILT |
513 | // low32 returns the least significant 32 bits of z. |
514 | func low32(z nat) uint32 { | |
515 | if len(z) == 0 { | |
516 | return 0 | |
517 | } | |
518 | return uint32(z[0]) | |
519 | } | |
520 | ||
521 | // low64 returns the least significant 64 bits of z. | |
522 | func low64(z nat) uint64 { | |
523 | if len(z) == 0 { | |
524 | return 0 | |
525 | } | |
526 | v := uint64(z[0]) | |
527 | if _W == 32 && len(z) > 1 { | |
528 | v |= uint64(z[1]) << 32 | |
529 | } | |
530 | return v | |
531 | } | |
532 | ||
adb0401d ILT |
533 | // Int64 returns the int64 representation of x. |
534 | // If x cannot be represented in an int64, the result is undefined. | |
7a938933 | 535 | func (x *Int) Int64() int64 { |
f8d9fa9e | 536 | v := int64(low64(x.abs)) |
7a938933 ILT |
537 | if x.neg { |
538 | v = -v | |
539 | } | |
540 | return v | |
541 | } | |
542 | ||
d6f2922e | 543 | // Uint64 returns the uint64 representation of x. |
be47d6ec | 544 | // If x cannot be represented in a uint64, the result is undefined. |
409a5e7e | 545 | func (x *Int) Uint64() uint64 { |
f8d9fa9e | 546 | return low64(x.abs) |
409a5e7e ILT |
547 | } |
548 | ||
7a938933 ILT |
549 | // SetString sets z to the value of s, interpreted in the given base, |
550 | // and returns z and a boolean indicating success. If SetString fails, | |
b740cb63 | 551 | // the value of z is undefined but the returned value is nil. |
7a938933 | 552 | // |
adb0401d ILT |
553 | // The base argument must be 0 or a value from 2 through MaxBase. If the base |
554 | // is 0, the string prefix determines the actual conversion base. A prefix of | |
555 | // ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a | |
556 | // ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10. | |
7a938933 ILT |
557 | // |
558 | func (z *Int) SetString(s string, base int) (*Int, bool) { | |
adb0401d ILT |
559 | r := strings.NewReader(s) |
560 | _, _, err := z.scan(r, base) | |
561 | if err != nil { | |
b740cb63 | 562 | return nil, false |
7a938933 | 563 | } |
adb0401d | 564 | _, _, err = r.ReadRune() |
2fd401c8 | 565 | if err != io.EOF { |
b740cb63 ILT |
566 | return nil, false |
567 | } | |
9c63abc9 | 568 | return z, true // err == io.EOF => scan consumed all of s |
7a938933 ILT |
569 | } |
570 | ||
8039ca76 ILT |
571 | // SetBytes interprets buf as the bytes of a big-endian unsigned |
572 | // integer, sets z to that value, and returns z. | |
573 | func (z *Int) SetBytes(buf []byte) *Int { | |
574 | z.abs = z.abs.setBytes(buf) | |
7a938933 ILT |
575 | z.neg = false |
576 | return z | |
577 | } | |
578 | ||
f038dae6 | 579 | // Bytes returns the absolute value of x as a big-endian byte slice. |
94252f4b ILT |
580 | func (x *Int) Bytes() []byte { |
581 | buf := make([]byte, len(x.abs)*_S) | |
582 | return buf[x.abs.bytes(buf):] | |
7a938933 ILT |
583 | } |
584 | ||
f038dae6 | 585 | // BitLen returns the length of the absolute value of x in bits. |
7a938933 | 586 | // The bit length of 0 is 0. |
94252f4b ILT |
587 | func (x *Int) BitLen() int { |
588 | return x.abs.bitLen() | |
7a938933 ILT |
589 | } |
590 | ||
fabcaa8d | 591 | // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. |
00d86ac9 | 592 | // If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. |
7a938933 ILT |
593 | // See Knuth, volume 2, section 4.6.3. |
594 | func (z *Int) Exp(x, y, m *Int) *Int { | |
00d86ac9 ILT |
595 | var yWords nat |
596 | if !y.neg { | |
597 | yWords = y.abs | |
7a938933 | 598 | } |
00d86ac9 | 599 | // y >= 0 |
7a938933 ILT |
600 | |
601 | var mWords nat | |
602 | if m != nil { | |
fabcaa8d | 603 | mWords = m.abs // m.abs may be nil for m == 0 |
7a938933 ILT |
604 | } |
605 | ||
00d86ac9 ILT |
606 | z.abs = z.abs.expNN(x.abs, yWords, mWords) |
607 | z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign | |
f8d9fa9e ILT |
608 | if z.neg && len(mWords) > 0 { |
609 | // make modulus result positive | |
610 | z.abs = z.abs.sub(mWords, z.abs) // z == x**y mod |m| && 0 <= z < |m| | |
611 | z.neg = false | |
612 | } | |
613 | ||
7a938933 ILT |
614 | return z |
615 | } | |
616 | ||
4ccad563 ILT |
617 | // GCD sets z to the greatest common divisor of a and b, which both must |
618 | // be > 0, and returns z. | |
94252f4b | 619 | // If x and y are not nil, GCD sets x and y such that z = a*x + b*y. |
4ccad563 | 620 | // If either a or b is <= 0, GCD sets z = x = y = 0. |
94252f4b | 621 | func (z *Int) GCD(x, y, a, b *Int) *Int { |
4ccad563 | 622 | if a.Sign() <= 0 || b.Sign() <= 0 { |
94252f4b | 623 | z.SetInt64(0) |
7a938933 ILT |
624 | if x != nil { |
625 | x.SetInt64(0) | |
626 | } | |
627 | if y != nil { | |
628 | y.SetInt64(0) | |
629 | } | |
94252f4b | 630 | return z |
7a938933 | 631 | } |
4ccad563 ILT |
632 | if x == nil && y == nil { |
633 | return z.binaryGCD(a, b) | |
634 | } | |
7a938933 ILT |
635 | |
636 | A := new(Int).Set(a) | |
637 | B := new(Int).Set(b) | |
638 | ||
639 | X := new(Int) | |
640 | Y := new(Int).SetInt64(1) | |
641 | ||
642 | lastX := new(Int).SetInt64(1) | |
643 | lastY := new(Int) | |
644 | ||
645 | q := new(Int) | |
646 | temp := new(Int) | |
647 | ||
648 | for len(B.abs) > 0 { | |
649 | r := new(Int) | |
650 | q, r = q.QuoRem(A, B, r) | |
651 | ||
652 | A, B = B, r | |
653 | ||
654 | temp.Set(X) | |
655 | X.Mul(X, q) | |
656 | X.neg = !X.neg | |
657 | X.Add(X, lastX) | |
658 | lastX.Set(temp) | |
659 | ||
660 | temp.Set(Y) | |
661 | Y.Mul(Y, q) | |
662 | Y.neg = !Y.neg | |
663 | Y.Add(Y, lastY) | |
664 | lastY.Set(temp) | |
665 | } | |
666 | ||
667 | if x != nil { | |
668 | *x = *lastX | |
669 | } | |
670 | ||
671 | if y != nil { | |
672 | *y = *lastY | |
673 | } | |
674 | ||
94252f4b ILT |
675 | *z = *A |
676 | return z | |
7a938933 ILT |
677 | } |
678 | ||
4ccad563 ILT |
679 | // binaryGCD sets z to the greatest common divisor of a and b, which both must |
680 | // be > 0, and returns z. | |
681 | // See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B. | |
682 | func (z *Int) binaryGCD(a, b *Int) *Int { | |
683 | u := z | |
684 | v := new(Int) | |
685 | ||
686 | // use one Euclidean iteration to ensure that u and v are approx. the same size | |
687 | switch { | |
688 | case len(a.abs) > len(b.abs): | |
689 | u.Set(b) | |
690 | v.Rem(a, b) | |
691 | case len(a.abs) < len(b.abs): | |
692 | u.Set(a) | |
693 | v.Rem(b, a) | |
694 | default: | |
695 | u.Set(a) | |
696 | v.Set(b) | |
697 | } | |
698 | ||
699 | // v might be 0 now | |
700 | if len(v.abs) == 0 { | |
701 | return u | |
702 | } | |
703 | // u > 0 && v > 0 | |
704 | ||
705 | // determine largest k such that u = u' << k, v = v' << k | |
706 | k := u.abs.trailingZeroBits() | |
707 | if vk := v.abs.trailingZeroBits(); vk < k { | |
708 | k = vk | |
709 | } | |
710 | u.Rsh(u, k) | |
711 | v.Rsh(v, k) | |
712 | ||
713 | // determine t (we know that u > 0) | |
714 | t := new(Int) | |
715 | if u.abs[0]&1 != 0 { | |
716 | // u is odd | |
717 | t.Neg(v) | |
718 | } else { | |
719 | t.Set(u) | |
720 | } | |
721 | ||
722 | for len(t.abs) > 0 { | |
723 | // reduce t | |
724 | t.Rsh(t, t.abs.trailingZeroBits()) | |
725 | if t.neg { | |
f038dae6 ILT |
726 | v, t = t, v |
727 | v.neg = len(v.abs) > 0 && !v.neg // 0 has no sign | |
4ccad563 | 728 | } else { |
f038dae6 | 729 | u, t = t, u |
4ccad563 ILT |
730 | } |
731 | t.Sub(u, v) | |
732 | } | |
733 | ||
f038dae6 | 734 | return z.Lsh(u, k) |
4ccad563 ILT |
735 | } |
736 | ||
94252f4b ILT |
737 | // ProbablyPrime performs n Miller-Rabin tests to check whether x is prime. |
738 | // If it returns true, x is prime with probability 1 - 1/4^n. | |
739 | // If it returns false, x is not prime. | |
740 | func (x *Int) ProbablyPrime(n int) bool { | |
741 | return !x.neg && x.abs.probablyPrime(n) | |
7a938933 ILT |
742 | } |
743 | ||
adb0401d | 744 | // Rand sets z to a pseudo-random number in [0, n) and returns z. |
7a938933 ILT |
745 | func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int { |
746 | z.neg = false | |
747 | if n.neg == true || len(n.abs) == 0 { | |
748 | z.abs = nil | |
749 | return z | |
750 | } | |
751 | z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen()) | |
752 | return z | |
753 | } | |
754 | ||
f8d9fa9e ILT |
755 | // ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ |
756 | // and returns z. If g and n are not relatively prime, the result is undefined. | |
757 | func (z *Int) ModInverse(g, n *Int) *Int { | |
7a938933 | 758 | var d Int |
f8d9fa9e ILT |
759 | d.GCD(z, nil, g, n) |
760 | // x and y are such that g*x + n*y = d. Since g and n are | |
761 | // relatively prime, d = 1. Taking that modulo n results in | |
762 | // g*x = 1, therefore x is the inverse element. | |
7a938933 | 763 | if z.neg { |
f8d9fa9e | 764 | z.Add(z, n) |
7a938933 ILT |
765 | } |
766 | return z | |
767 | } | |
768 | ||
7a938933 ILT |
769 | // Lsh sets z = x << n and returns z. |
770 | func (z *Int) Lsh(x *Int, n uint) *Int { | |
771 | z.abs = z.abs.shl(x.abs, n) | |
772 | z.neg = x.neg | |
773 | return z | |
774 | } | |
775 | ||
7a938933 ILT |
776 | // Rsh sets z = x >> n and returns z. |
777 | func (z *Int) Rsh(x *Int, n uint) *Int { | |
778 | if x.neg { | |
779 | // (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1) | |
780 | t := z.abs.sub(x.abs, natOne) // no underflow because |x| > 0 | |
781 | t = t.shr(t, n) | |
782 | z.abs = t.add(t, natOne) | |
783 | z.neg = true // z cannot be zero if x is negative | |
784 | return z | |
785 | } | |
786 | ||
787 | z.abs = z.abs.shr(x.abs, n) | |
788 | z.neg = false | |
789 | return z | |
790 | } | |
791 | ||
94252f4b ILT |
792 | // Bit returns the value of the i'th bit of x. That is, it |
793 | // returns (x>>i)&1. The bit index i must be >= 0. | |
794 | func (x *Int) Bit(i int) uint { | |
4ccad563 ILT |
795 | if i == 0 { |
796 | // optimization for common case: odd/even test of x | |
797 | if len(x.abs) > 0 { | |
798 | return uint(x.abs[0] & 1) // bit 0 is same for -x | |
799 | } | |
800 | return 0 | |
801 | } | |
adb0401d ILT |
802 | if i < 0 { |
803 | panic("negative bit index") | |
804 | } | |
94252f4b ILT |
805 | if x.neg { |
806 | t := nat(nil).sub(x.abs, natOne) | |
adb0401d ILT |
807 | return t.bit(uint(i)) ^ 1 |
808 | } | |
809 | ||
94252f4b | 810 | return x.abs.bit(uint(i)) |
adb0401d ILT |
811 | } |
812 | ||
ab61e9c4 | 813 | // SetBit sets z to x, with x's i'th bit set to b (0 or 1). |
be47d6ec ILT |
814 | // That is, if b is 1 SetBit sets z = x | (1 << i); |
815 | // if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1, | |
adb0401d ILT |
816 | // SetBit will panic. |
817 | func (z *Int) SetBit(x *Int, i int, b uint) *Int { | |
818 | if i < 0 { | |
819 | panic("negative bit index") | |
820 | } | |
821 | if x.neg { | |
822 | t := z.abs.sub(x.abs, natOne) | |
823 | t = t.setBit(t, uint(i), b^1) | |
824 | z.abs = t.add(t, natOne) | |
825 | z.neg = len(z.abs) > 0 | |
826 | return z | |
827 | } | |
828 | z.abs = z.abs.setBit(x.abs, uint(i), b) | |
829 | z.neg = false | |
830 | return z | |
831 | } | |
7a938933 ILT |
832 | |
833 | // And sets z = x & y and returns z. | |
834 | func (z *Int) And(x, y *Int) *Int { | |
835 | if x.neg == y.neg { | |
836 | if x.neg { | |
837 | // (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1) | |
ab61e9c4 ILT |
838 | x1 := nat(nil).sub(x.abs, natOne) |
839 | y1 := nat(nil).sub(y.abs, natOne) | |
7a938933 ILT |
840 | z.abs = z.abs.add(z.abs.or(x1, y1), natOne) |
841 | z.neg = true // z cannot be zero if x and y are negative | |
842 | return z | |
843 | } | |
844 | ||
845 | // x & y == x & y | |
846 | z.abs = z.abs.and(x.abs, y.abs) | |
847 | z.neg = false | |
848 | return z | |
849 | } | |
850 | ||
851 | // x.neg != y.neg | |
852 | if x.neg { | |
853 | x, y = y, x // & is symmetric | |
854 | } | |
855 | ||
856 | // x & (-y) == x & ^(y-1) == x &^ (y-1) | |
ab61e9c4 | 857 | y1 := nat(nil).sub(y.abs, natOne) |
7a938933 ILT |
858 | z.abs = z.abs.andNot(x.abs, y1) |
859 | z.neg = false | |
860 | return z | |
861 | } | |
862 | ||
7a938933 ILT |
863 | // AndNot sets z = x &^ y and returns z. |
864 | func (z *Int) AndNot(x, y *Int) *Int { | |
865 | if x.neg == y.neg { | |
866 | if x.neg { | |
867 | // (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1) | |
ab61e9c4 ILT |
868 | x1 := nat(nil).sub(x.abs, natOne) |
869 | y1 := nat(nil).sub(y.abs, natOne) | |
7a938933 ILT |
870 | z.abs = z.abs.andNot(y1, x1) |
871 | z.neg = false | |
872 | return z | |
873 | } | |
874 | ||
875 | // x &^ y == x &^ y | |
876 | z.abs = z.abs.andNot(x.abs, y.abs) | |
877 | z.neg = false | |
878 | return z | |
879 | } | |
880 | ||
881 | if x.neg { | |
882 | // (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1) | |
ab61e9c4 | 883 | x1 := nat(nil).sub(x.abs, natOne) |
7a938933 ILT |
884 | z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne) |
885 | z.neg = true // z cannot be zero if x is negative and y is positive | |
886 | return z | |
887 | } | |
888 | ||
889 | // x &^ (-y) == x &^ ^(y-1) == x & (y-1) | |
c271e224 | 890 | y1 := nat(nil).sub(y.abs, natOne) |
7a938933 ILT |
891 | z.abs = z.abs.and(x.abs, y1) |
892 | z.neg = false | |
893 | return z | |
894 | } | |
895 | ||
7a938933 ILT |
896 | // Or sets z = x | y and returns z. |
897 | func (z *Int) Or(x, y *Int) *Int { | |
898 | if x.neg == y.neg { | |
899 | if x.neg { | |
900 | // (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1) | |
ab61e9c4 ILT |
901 | x1 := nat(nil).sub(x.abs, natOne) |
902 | y1 := nat(nil).sub(y.abs, natOne) | |
7a938933 ILT |
903 | z.abs = z.abs.add(z.abs.and(x1, y1), natOne) |
904 | z.neg = true // z cannot be zero if x and y are negative | |
905 | return z | |
906 | } | |
907 | ||
908 | // x | y == x | y | |
909 | z.abs = z.abs.or(x.abs, y.abs) | |
910 | z.neg = false | |
911 | return z | |
912 | } | |
913 | ||
914 | // x.neg != y.neg | |
915 | if x.neg { | |
916 | x, y = y, x // | is symmetric | |
917 | } | |
918 | ||
919 | // x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1) | |
ab61e9c4 | 920 | y1 := nat(nil).sub(y.abs, natOne) |
7a938933 ILT |
921 | z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne) |
922 | z.neg = true // z cannot be zero if one of x or y is negative | |
923 | return z | |
924 | } | |
925 | ||
7a938933 ILT |
926 | // Xor sets z = x ^ y and returns z. |
927 | func (z *Int) Xor(x, y *Int) *Int { | |
928 | if x.neg == y.neg { | |
929 | if x.neg { | |
930 | // (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1) | |
ab61e9c4 ILT |
931 | x1 := nat(nil).sub(x.abs, natOne) |
932 | y1 := nat(nil).sub(y.abs, natOne) | |
7a938933 ILT |
933 | z.abs = z.abs.xor(x1, y1) |
934 | z.neg = false | |
935 | return z | |
936 | } | |
937 | ||
938 | // x ^ y == x ^ y | |
939 | z.abs = z.abs.xor(x.abs, y.abs) | |
940 | z.neg = false | |
941 | return z | |
942 | } | |
943 | ||
944 | // x.neg != y.neg | |
945 | if x.neg { | |
946 | x, y = y, x // ^ is symmetric | |
947 | } | |
948 | ||
949 | // x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1) | |
ab61e9c4 | 950 | y1 := nat(nil).sub(y.abs, natOne) |
7a938933 ILT |
951 | z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne) |
952 | z.neg = true // z cannot be zero if only one of x or y is negative | |
953 | return z | |
954 | } | |
955 | ||
7a938933 ILT |
956 | // Not sets z = ^x and returns z. |
957 | func (z *Int) Not(x *Int) *Int { | |
958 | if x.neg { | |
959 | // ^(-x) == ^(^(x-1)) == x-1 | |
960 | z.abs = z.abs.sub(x.abs, natOne) | |
961 | z.neg = false | |
962 | return z | |
963 | } | |
964 | ||
965 | // ^x == -x-1 == -(x+1) | |
966 | z.abs = z.abs.add(x.abs, natOne) | |
967 | z.neg = true // z cannot be zero if x is positive | |
968 | return z | |
969 | } | |
8039ca76 | 970 | |
8039ca76 | 971 | // Gob codec version. Permits backward-compatible changes to the encoding. |
adb0401d | 972 | const intGobVersion byte = 1 |
8039ca76 ILT |
973 | |
974 | // GobEncode implements the gob.GobEncoder interface. | |
94252f4b | 975 | func (x *Int) GobEncode() ([]byte, error) { |
f038dae6 ILT |
976 | if x == nil { |
977 | return nil, nil | |
978 | } | |
94252f4b ILT |
979 | buf := make([]byte, 1+len(x.abs)*_S) // extra byte for version and sign bit |
980 | i := x.abs.bytes(buf) - 1 // i >= 0 | |
adb0401d | 981 | b := intGobVersion << 1 // make space for sign bit |
94252f4b | 982 | if x.neg { |
8039ca76 ILT |
983 | b |= 1 |
984 | } | |
985 | buf[i] = b | |
986 | return buf[i:], nil | |
987 | } | |
988 | ||
8039ca76 | 989 | // GobDecode implements the gob.GobDecoder interface. |
2fd401c8 | 990 | func (z *Int) GobDecode(buf []byte) error { |
8039ca76 | 991 | if len(buf) == 0 { |
f038dae6 ILT |
992 | // Other side sent a nil or default value. |
993 | *z = Int{} | |
994 | return nil | |
8039ca76 ILT |
995 | } |
996 | b := buf[0] | |
adb0401d | 997 | if b>>1 != intGobVersion { |
2fd401c8 | 998 | return errors.New(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1)) |
8039ca76 ILT |
999 | } |
1000 | z.neg = b&1 != 0 | |
1001 | z.abs = z.abs.setBytes(buf[1:]) | |
1002 | return nil | |
1003 | } | |
4ccad563 ILT |
1004 | |
1005 | // MarshalJSON implements the json.Marshaler interface. | |
6736ef96 | 1006 | func (z *Int) MarshalJSON() ([]byte, error) { |
4ccad563 | 1007 | // TODO(gri): get rid of the []byte/string conversions |
6736ef96 | 1008 | return []byte(z.String()), nil |
4ccad563 ILT |
1009 | } |
1010 | ||
1011 | // UnmarshalJSON implements the json.Unmarshaler interface. | |
6736ef96 | 1012 | func (z *Int) UnmarshalJSON(text []byte) error { |
4ccad563 | 1013 | // TODO(gri): get rid of the []byte/string conversions |
6736ef96 ILT |
1014 | if _, ok := z.SetString(string(text), 0); !ok { |
1015 | return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) | |
1016 | } | |
1017 | return nil | |
1018 | } | |
1019 | ||
f8d9fa9e | 1020 | // MarshalText implements the encoding.TextMarshaler interface. |
6736ef96 ILT |
1021 | func (z *Int) MarshalText() (text []byte, err error) { |
1022 | return []byte(z.String()), nil | |
1023 | } | |
1024 | ||
f8d9fa9e | 1025 | // UnmarshalText implements the encoding.TextUnmarshaler interface. |
6736ef96 ILT |
1026 | func (z *Int) UnmarshalText(text []byte) error { |
1027 | if _, ok := z.SetString(string(text), 0); !ok { | |
1028 | return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) | |
4ccad563 ILT |
1029 | } |
1030 | return nil | |
1031 | } |