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/CAOXNBZRw27kJkxzXJE8emV4o2OFSjTkc%2B65dJnJBT-b%2B%2BnoZJQ%40mail.gmail.com.
