I'm equally curious.
FWIW, I realized the loop should perhaps be
```
mb := nat(nil).setUint64(b) // ensure mb starts big enough for b, even on
32-bit arch
for m := a + 1; m <= b; m++ {
mb.setUint64(m)
z = z.mul(z, mb)
}
```
to avoid allocating repeatedly for `m`, which yields:
BenchmarkIterativeMulRangeN-10 354685 3032 ns/op 2129 B/op
48 allocs/op
On Sun, Jan 7, 2024 at 2:41 AM Rob Pike <r...@golang.org> wrote:
> It seems reasonable but first I'd like to understand why the recursive
> method is used. I can't deduce why, but the CL that adds it, by gri, does
> Karatsuba multiplication, which implies something deep is going on. I'll
> add him to the conversation.
>
> -rob
>
>
>
>
> On Sun, Jan 7, 2024 at 5:46 PM John Jannotti <janno...@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?)
>>
>>
>>
>> --
>> 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 golang-nuts+unsubscr...@googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/golang-nuts/e6ceb75a-f8b7-4f77-97dc-9445fb750782n%40googlegroups.com
>> <https://groups.google.com/d/msgid/golang-nuts/e6ceb75a-f8b7-4f77-97dc-9445fb750782n%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>
--
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 golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/CALZHwkqd7ZQ6_VxYBJx8GWMjTLcqGo-3ausEC9rc21z3nHjyQA%40mail.gmail.com.
