diff options
author | Katie Hockman <katie@golang.org> | 2021-01-27 10:33:35 -0500 |
---|---|---|
committer | Katie Hockman <katie@golang.org> | 2021-02-03 15:04:02 +0000 |
commit | e491c6eea9ad599a0ae766a3217bd9a16ca3a25a (patch) | |
tree | 21262a678175e8abc31b4df1da1eabbc5d43bbef | |
parent | fca94ab3ab113ceddb7934f76d0f1660cad98260 (diff) | |
download | go-e491c6eea9ad599a0ae766a3217bd9a16ca3a25a.tar.gz go-e491c6eea9ad599a0ae766a3217bd9a16ca3a25a.zip |
math/big: fix comment in divRecursiveStep
There appears to be a typo in the description of
the recursive division algorithm.
Two things seem suspicious with the original comment:
1. It is talking about choosing s, but s doesn't
appear anywhere in the equation.
2. The math in the equation is incorrect.
Where
B = len(v)/2
s = B - 1
Proof that it is incorrect:
len(v) - B >= B + 1
len(v) - len(v)/2 >= len(v)/2 + 1
This doesn't hold if len(v) is even, e.g. 10:
10 - 10/2 >= 10/2 + 1
10 - 5 >= 5 + 1
5 >= 6 // this is false
The new equation will be the following,
which will be mathematically correct:
len(v) - s >= B + 1
len(v) - (len(v)/2 - 1) >= len(v)/2 + 1
len(v) - len(v)/2 + 1 >= len(v)/2 + 1
len(v) - len(v)/2 >= len(v)/2
This holds if len(v) is even or odd.
e.g. 10
10 - 10/2 >= 10/2
10 - 5 >= 5
5 >= 5
e.g. 11
11 - 11/2 >= 11/2
11 - 5 >= 5
6 >= 5
Change-Id: If77ce09286cf7038637b5dfd0fb7d4f828023f56
Reviewed-on: https://go-review.googlesource.com/c/go/+/287372
Run-TryBot: Katie Hockman <katie@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
Trust: Katie Hockman <katie@golang.org>
-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 068176e1c1..bbd6c8850b 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -881,7 +881,7 @@ func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat) { // then floor(u1/v1) >= floor(u/v) // // Moreover, the difference is at most 2 if len(v1) >= len(u/v) - // We choose s = B-1 since len(v)-B >= B+1 >= len(u/v) + // We choose s = B-1 since len(v)-s >= B+1 >= len(u/v) s := (B - 1) // Except for the first step, the top bits are always // a division remainder, so the quotient length is <= n. |