From 1d992f2e369e7e518ff57cd7508a15442d5df186 Mon Sep 17 00:00:00 2001 From: Juraj Sukop Date: Wed, 27 Feb 2019 17:43:46 +0000 Subject: [PATCH] math/big: better initial guess for nat.sqrt MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The proposed change introduces a better initial guess which is closer to the final value and therefore converges in fewer steps. Consider for example sqrt(8): previously the guess was 8, whereas now it is 4 (and the result is 2). All this change does is it computes the division by two more accurately while it keeps the guess ≥ √x. Change-Id: I917248d734a7b0488d14a647a063f674e56c4e30 GitHub-Last-Rev: c06d9d4876c8e7d6739f0e4b687e370fe1e9aad7 GitHub-Pull-Request: golang/go#28981 Reviewed-on: https://go-review.googlesource.com/c/163866 Run-TryBot: Brad Fitzpatrick TryBot-Result: Gobot Gobot Reviewed-by: Robert Griesemer --- src/math/big/nat.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 1e4a3b09cf..336633a2fa 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -1345,7 +1345,7 @@ func (z nat) sqrt(x nat) nat { var z1, z2 nat z1 = z z1 = z1.setUint64(1) - z1 = z1.shl(z1, uint(x.bitLen()/2+1)) // must be ≥ √x + z1 = z1.shl(z1, uint(x.bitLen()+1)/2) // must be ≥ √x for n := 0; ; n++ { z2, _ = z2.div(nil, x, z1) z2 = z2.add(z2, z1) -- 2.48.1