I enjoy bignum implementations, so I was looking through nat.go and saw
that `mulRange` is implemented in a surprising, recursive way,. In the
non-base case, `mulRange(a, b)` returns `mulrange(a, (a+b)/2) *
mulRange(1+(a+b)/2, b)` (lots of big.Int ceremony elided).
That's fine, but I didn't see any advantage over the straightforward (and
simpler?) for loop.
```
z = z.setUint64(a)
for m := a + 1; m <= b; m++ {
z = z.mul(z, nat(nil).setUint64(m))
}
return z
```
In fact, I suspected the existing code was slower, and allocated a lot
more. That seems true. A quick benchmark, using the existing unit test as
the benchmark, yields
BenchmarkRecusiveMulRangeN-10 169417 6856 ns/op 9452 B/op
338 allocs/op
BenchmarkIterativeMulRangeN-10 265354 4269 ns/op 2505 B/op
196 allocs/op
I doubt `mulRange` is a performance bottleneck in anyone's code! But it is
exported as `int.MulRange` so I guess it's viewed with some value. And
seeing as how the for-loop seems even easier to understand that the
recursive version, maybe it's worth submitting a PR? (If so, should I
create an issue first?)
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/e6ceb75a-f8b7-4f77-97dc-9445fb750782n%40googlegroups.com.
