Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <CAM7=BFoktwgy=T0GK6Mpmp2gYToCUs=CrM29MRWw8O7TPypQ8w@mail.gmail.com>
 <CAHp75Vf8kQ73w0R9ieDNjDVkxM-V83QRN9mc6BjRZA8xHpPNAA@mail.gmail.com>
 <CAHp75Vft8pnA+m0C=Ok7nRyjERAd2uJJ4q6HcN460j0Hir6Kaw@mail.gmail.com>
 <CAM7=BFoH7Q+YHvPFnHM4j72ORHQp4gTjHFjnfeLsV2-30ZLNYw@mail.gmail.com>
 <CA+7tXigG7QVYOtkuFrqciHfuxE4+c0JM9z8r0e9rooTjjz5PYA@mail.gmail.com> <CAHp75VdeSkQSHjwTFObj84TyOOW2dh9LW3Ci9L7=iDFTbEvRoA@mail.gmail.com>
In-Reply-To: <CAHp75VdeSkQSHjwTFObj84TyOOW2dh9LW3Ci9L7=iDFTbEvRoA@mail.gmail.com>
From:   Trent Piepho <tpiepho@gmail.com>
Date:   Sat, 22 May 2021 17:05:08 -0700
Message-ID: <CA+7tXijWgDGzWPOYhzX+bWn0cjOZ9y1-gWRG+0uobQ128=8vCg@mail.gmail.com>
Subject: Re: A divide by zero bug in lib/math/rational.c (with triggering input)
To:     Andy Shevchenko <andy.shevchenko@gmail.com>
Cc:     Daniel Latypov <dlatypov@google.com>,
        Yiyuan guo <yguoaz@gmail.com>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        "andy@kernel.org" <andy@kernel.org>,
        "akpm@linux-foundation.org" <akpm@linux-foundation.org>,
        "oskar@scara.com" <oskar@scara.com>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Fri, May 21, 2021 at 2:53 AM Andy Shevchenko
<andy.shevchenko@gmail.com> wrote:
> >
> > I think the error can only occur when the loop exits on the 1st
> > iteration, when d1 is still zero.  In this case the prior convergent,
> > n1/d1 = 1/0, does not really exist as this is the 1st iteration.  The
> > actual series of convergents generated will never have zero terms,
> > because we stop at zero, so there will never be zero from the prior
> > iteration as we would have stopped there.
>
> This is my conclusion as well, but you beat me to it.
> And below is exactly my understanding of what's going on.

I came up with some more test cases, and there is another possibility,
if the value is small. e.g.

rational_best_approximation(1,30, 1,10, ...)
rational_best_approximation(1,19, 1,10, ...)

The former should be 0/1 and the latter 1/10.  These will divide by
zero on the 2nd iteration.

But I have a patch now that works.  It gets the closest answer in all
cases, larger than max, less than min but closer to the min than to
zero, and closest to zero.

It ends up being zero additional arithmetic to do this.   All that is
needed is a few additional branches in the termination condition.