math/big: improve performance of nat.mulRange

On Sun, Jan 7, 2024 at 5:46 PM John Jannotti <jannotti@gmail.com> wrote: 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?)