From 2955a8a6cccc4afe53da266bbb0b8f6fe52974aa Mon Sep 17 00:00:00 2001 From: Brian Kessler Date: Mon, 13 Nov 2017 22:05:45 -0800 Subject: [PATCH] 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 --- src/math/big/int.go | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) 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 -- 2.50.0