diff options
| author | Juraj Sukop <sukop@users.noreply.github.com> | 2019-02-27 17:43:46 +0000 |
|---|---|---|
| committer | Brad Fitzpatrick <bradfitz@golang.org> | 2019-02-27 18:48:56 +0000 |
| commit | 1d992f2e369e7e518ff57cd7508a15442d5df186 (patch) | |
| tree | e1e3457d4f71a896c373fca7504cf3cbf3e13a6e /src/math/big | |
| parent | 9650726e79e20386b59b253e98dcaaa768e06c95 (diff) | |
| download | go-1d992f2e369e7e518ff57cd7508a15442d5df186.tar.xz | |
math/big: better initial guess for nat.sqrt
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 <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src/math/big')
| -rw-r--r-- | src/math/big/nat.go | 2 |
1 files changed, 1 insertions, 1 deletions
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) |