Messages in this thread | | | From | Trent Piepho <> | Date | Mon, 24 May 2021 13:17:48 -0700 | Subject | Re: [PATCH] lib/math/rational.c: Fix divide by zero |
| |
On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko <andriy.shevchenko@intel.com> wrote: > On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote: > > This misses the test cases (*). Please, develop them with Daniel. > > *) We usually don't accept changes in the generic libraries without test cases. > > Fixes tag?
Is there a bug report on a tracker? I just got the email from Yigua.
> > + /* This tests if the semi-convergent is closer than the previous > > + * convergent. If d1 is zero there is no previous convergent as this > > + * is the 1st iteration, so always choose the semi-convergent. > > */ > > - if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) { > > + if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) { > > n1 = n0 + t * n1; > > d1 = d0 + t * d1; > > } > > I think that refactoring may lead us to check first iteration before even going > into the loop. But it's another story and we may do it later (the algo uses
I started that, but it had no advantages and some disadvantages.
Basically, there are three cases: too large, too small & closest to zero, too small & closest to non-zero. This code can handle those three cases by adding three branches, if(d1), if(n1), and if(!d1). The truth values we need already exist at this point the algorithm.
If it's at the start, then there still needs to be the three branches for each case. But the values to test must be calculated too.
What's more, it's possible that the value is exactly representable in the allowed range. That's actual appears to be the most common use case, reducing a fraction to lowest terms (*). By putting the tests in the "terminate because of limits" case, they don't need to happen when "terminate because exact value find" is the result. If the check was first, then it would always happen, even if it wouldn't have been necessary.
And the time it took to find this bug shows us that out of bounds inputs are not a common case, so putting that on the hot path by checking it first at the expense of the reducing to lowest terms path doesn't make sense.
(*) One could write a reduce to lowest terms function with an easier interface. It could be a trivial one expression wrapper around rational_best_approximation(). It could also be a simpler function, but I think it would still perform the exact same sequence of divisions and moduli, so it wouldn't really make any difference.
| |