Possible Bug or Typo

[Niels Möller]

Brett Kuntz <kuntz at shaw.ca> writes:

> As you can see both are defined as "(3 * (an) + GMP_NUMB_BITS)". I am
> only bringing this up as the commenting for 3 is "Scratch need is
> 5an/2 + 10k, k is the recursion depth" and the commenting for 4 is
> "Scratch need is 8an/3 + 13k, k is the recursion depth".
>
> So my question is was the mpn_toom4_sqr_itch() define supposed to use
> different (larger) numbers than the mpn_toom3_sqr_itch() define?

In both cases, the linear coeffient is rounded up to 3 (from 5/2 and 8/3
respectively), and the logarithmic term (k = O(log n)) is replaced by a
constant. I agree it looks a bit adhoc, but would need a bit more
analysis to say if there's a problem.

Looks like Marco increased the toom3 values slightly in 2012, to support
larger n.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.