On Sun, Jun 23, 2024 at 09:00:29AM +0200, Joel Jacobson wrote: > Attached, rebased version of the patch that implements the Karatsuba > algorithm in numeric.c's mul_var().
It's one of these areas where Dean Rasheed would be a good match for a review, so adding him in CC. He has been doing a lot of stuff in this area over the years. +#define KARATSUBA_BASE_LIMIT 384 +#define KARATSUBA_VAR1_MIN1 128 +#define KARATSUBA_VAR1_MIN2 2000 +#define KARATSUBA_VAR2_MIN1 2500 +#define KARATSUBA_VAR2_MIN2 9000 +#define KARATSUBA_SLOPE 0.764 +#define KARATSUBA_INTERCEPT 90.737 These numbers feel magic, and there are no explanations behind these choices so it is hard to know whether these are good or not, or if there are potentially "better" choices. I'd suggest to explain why these variables are here as well as the basics of the method in this area of the code, with the function doing the operation pointing at that so as all the explanations are in a single place. Okay, these are thresholds based on the number of digits to decide if the normal or Karatsuba's method should be used, but grouping all the explanations in a single place is simpler. I may have missed something, but did you do some benchmark when the thresholds are at their limit where we would fallback to the calculation method of HEAD? I guess that the answer to my question of "Is HEAD performing better across these thresholds?" is clearly "no" based on what I read at [1] and the threshold numbers chosen, still asking. [1]: https://en.wikipedia.org/wiki/Karatsuba_algorithm -- Michael
signature.asc
Description: PGP signature
