Actually, both implementations have bugs!
The recursive implementation ends with:
```
m := (a + b) / 2
return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
```
That's a bug whenever `(a+b)` overflows, making `m` small.
FIX: `m := a + (b-a)/2`
My iterative implementation went into an infinite loop here:
`for m := a + 1; m <= b; m++ {`
if b is `math.MaxUint64`
FIX: add `&& m > a` to the exit condition is an easy fix, but pays a small
penalty for the vast majority of calls that don't have b=MaxUint64
I would add these to `mulRangesN` of the unit test:
```
{math.MaxUint64 - 3, math.MaxUint64 - 1,
"6277101735386680760773248120919220245411599323494568951784"},
{math.MaxUint64 - 3, math.MaxUint64,
"115792089237316195360799967654821100226821973275796746098729803619699194331160"}
```
On Sun, Jan 7, 2024 at 6:34 AM John Jannotti <janno...@gmail.com> wrote:
> 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/CALZHwko9GC7C_JThfVdFxBQtCmu9%2B%2BNYun8Tope4608oiio_6g%40mail.gmail.com.
