Brett Kuntz <[email protected]> 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. _______________________________________________ gmp-bugs mailing list [email protected] https://gmplib.org/mailman/listinfo/gmp-bugs
