diff options
| author | Brian Kessler <brian.m.kessler@gmail.com> | 2017-11-13 22:05:45 -0800 |
|---|---|---|
| committer | Robert Griesemer <gri@golang.org> | 2017-11-14 17:32:39 +0000 |
| commit | 2955a8a6cccc4afe53da266bbb0b8f6fe52974aa (patch) | |
| tree | 5b44fec8bf0dff4a170289f19c1ffcae1dfc0e03 /src | |
| parent | 5ea2360b6643ec53018b1c080f4824b8238bff3a (diff) | |
| download | go-2955a8a6cccc4afe53da266bbb0b8f6fe52974aa.tar.xz | |
math/big: clarify comment on lehmerGCD overflow
A clarifying comment was added to indicate that overflow of a
single Word is not possible in the single digit calculation.
Lehmer's paper includes a proof of the bounds on the size of the
cosequences (u0, u1, u2, v0, v1, v2).
Change-Id: I98127a07aa8f8fe44814b74b2bc6ff720805194b
Reviewed-on: https://go-review.googlesource.com/77451
Reviewed-by: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src')
| -rw-r--r-- | src/math/big/int.go | 5 |
1 files changed, 4 insertions, 1 deletions
diff --git a/src/math/big/int.go b/src/math/big/int.go index a89f7a2d17..135ebd083f 100644 --- a/src/math/big/int.go +++ b/src/math/big/int.go @@ -581,7 +581,10 @@ func (z *Int) lehmerGCD(a, b *Int) *Int { u0, u1, u2 = 0, 1, 0 v0, v1, v2 = 0, 0, 1 - // calculate the quotient and cosequences using Collins' stopping condition + // Calculate the quotient and cosequences using Collins' stopping condition. + // Note that overflow of a Word is not possible when computing the remainder + // sequence and cosequences since the cosequence size is bounded by the input size. + // See section 4.2 of Jebelean for details. for a2 >= v2 && a1-a2 >= v1+v2 { q := a1 / a2 a1, a2 = a2, a1-q*a2 |