Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(2596)

Side by Side Diff: src/pkg/big/int.go

Issue 1004042: code review 1004042: big: implemented Karatsuba multiplication (Closed)
Patch Set: code review 1004042: big: implemented Karatsuba multiplication Created 13 years, 11 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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 }
OLDNEW
« no previous file with comments | « src/pkg/big/calibrate_test.go ('k') | src/pkg/big/int_test.go » ('j') | src/pkg/big/nat.go » ('J')

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b