OLD | NEW |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // This file implements signed multi-precision integers. | 5 // This file implements signed multi-precision integers. |
6 | 6 |
7 package big | 7 package big |
8 | 8 |
9 // An Int represents a signed multi-precision integer. | 9 // An Int represents a signed multi-precision integer. |
10 // The zero value for an Int represents the value 0. | 10 // The zero value for an Int represents the value 0. |
(...skipping 212 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
223 z.neg = false | 223 z.neg = false |
224 z.abs = nil | 224 z.abs = nil |
225 return nil, false | 225 return nil, false |
226 } | 226 } |
227 | 227 |
228 | 228 |
229 // SetBytes interprets b as the bytes of a big-endian, unsigned integer and | 229 // SetBytes interprets b as the bytes of a big-endian, unsigned integer and |
230 // sets z to that value. | 230 // sets z to that value. |
231 func (z *Int) SetBytes(b []byte) *Int { | 231 func (z *Int) SetBytes(b []byte) *Int { |
232 s := int(_S) | 232 s := int(_S) |
233 » z.abs = z.abs.make((len(b)+s-1)/s, false) | 233 » z.abs = z.abs.make((len(b) + s - 1) / s) |
234 z.neg = false | 234 z.neg = false |
235 | 235 |
236 j := 0 | 236 j := 0 |
237 for len(b) >= s { | 237 for len(b) >= s { |
238 var w Word | 238 var w Word |
239 | 239 |
240 for i := s; i > 0; i-- { | 240 for i := s; i > 0; i-- { |
241 w <<= 8 | 241 w <<= 8 |
242 w |= Word(b[len(b)-i]) | 242 w |= Word(b[len(b)-i]) |
243 } | 243 } |
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
379 // ProbablyPrime performs n Miller-Rabin tests to check whether z is prime. | 379 // ProbablyPrime performs n Miller-Rabin tests to check whether z is prime. |
380 // If it returns true, z is prime with probability 1 - 1/4^n. | 380 // If it returns true, z is prime with probability 1 - 1/4^n. |
381 // If it returns false, z is not prime. | 381 // If it returns false, z is not prime. |
382 func ProbablyPrime(z *Int, n int) bool { return !z.neg && z.abs.probablyPrime(n)
} | 382 func ProbablyPrime(z *Int, n int) bool { return !z.neg && z.abs.probablyPrime(n)
} |
383 | 383 |
384 | 384 |
385 // Lsh sets z = x << n and returns z. | 385 // Lsh sets z = x << n and returns z. |
386 func (z *Int) Lsh(x *Int, n uint) *Int { | 386 func (z *Int) Lsh(x *Int, n uint) *Int { |
387 addedWords := int(n) / _W | 387 addedWords := int(n) / _W |
388 // Don't assign z.abs yet, in case z == x | 388 // Don't assign z.abs yet, in case z == x |
389 » znew := z.abs.make(len(x.abs)+addedWords+1, false) | 389 » znew := z.abs.make(len(x.abs) + addedWords + 1) |
390 z.neg = x.neg | 390 z.neg = x.neg |
391 znew[addedWords:].shiftLeft(x.abs, n%_W) | 391 znew[addedWords:].shiftLeft(x.abs, n%_W) |
392 for i := range znew[0:addedWords] { | 392 for i := range znew[0:addedWords] { |
393 znew[i] = 0 | 393 znew[i] = 0 |
394 } | 394 } |
395 z.abs = znew.norm() | 395 z.abs = znew.norm() |
396 return z | 396 return z |
397 } | 397 } |
398 | 398 |
399 | 399 |
400 // Rsh sets z = x >> n and returns z. | 400 // Rsh sets z = x >> n and returns z. |
401 func (z *Int) Rsh(x *Int, n uint) *Int { | 401 func (z *Int) Rsh(x *Int, n uint) *Int { |
402 removedWords := int(n) / _W | 402 removedWords := int(n) / _W |
403 // Don't assign z.abs yet, in case z == x | 403 // Don't assign z.abs yet, in case z == x |
404 » znew := z.abs.make(len(x.abs)-removedWords, false) | 404 » znew := z.abs.make(len(x.abs) - removedWords) |
405 z.neg = x.neg | 405 z.neg = x.neg |
406 znew.shiftRight(x.abs[removedWords:], n%_W) | 406 znew.shiftRight(x.abs[removedWords:], n%_W) |
407 z.abs = znew.norm() | 407 z.abs = znew.norm() |
408 return z | 408 return z |
409 } | 409 } |
OLD | NEW |