From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3CCB8C2B9F2 for ; Sun, 23 May 2021 00:05:24 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 00F94610A2 for ; Sun, 23 May 2021 00:05:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231477AbhEWAGr (ORCPT ); Sat, 22 May 2021 20:06:47 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34210 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231440AbhEWAGr (ORCPT ); Sat, 22 May 2021 20:06:47 -0400 Received: from mail-ej1-x632.google.com (mail-ej1-x632.google.com [IPv6:2a00:1450:4864:20::632]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8D723C061574 for ; Sat, 22 May 2021 17:05:20 -0700 (PDT) Received: by mail-ej1-x632.google.com with SMTP id f18so5878036ejq.10 for ; Sat, 22 May 2021 17:05:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=ivy3nqszZrnAQTpRgs8RLYL4mi7jLAex7afb3rEY1SQ=; b=hl8pIV4DGQ7pBk1r9cmtUYmm1pYEbtLnN5Ac5BXtihF0NTCMncOmcVvX8IcnVnAMb8 cPsDij7iGH0XsJlAqf+O19iN2NX7yle88E3UHZ70FdyrvDUcVDB2mXdT0KuPcu2CfOmu Y0VbWcSLqaNks7wtKQHIYVFw+exvz2pf7gCSvwlMCnpS5GU5fFi8eNLm2EJeso+Qk2Cm q/L7VPpJfTAB1U5CDvtl7h15eVRm7jx4CeKN5A1KCCP7crrzbOLiP7TTeGFhFsyxrt/q zBx4e7CfdfBcfWIE0ANmq1y8us3hvLeU8ljIjypvQZk54/cy9WvFBP1Td+iVUrzxLC3e XuWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ivy3nqszZrnAQTpRgs8RLYL4mi7jLAex7afb3rEY1SQ=; b=QF/l4JhG6mrjpoERxzjMzjpUH1hKdYp4t9KEweg2ChnnqESvnmMZ/V+59MWJYcDWeC +fcEe2+O/hL24FVwCOJK/QhNgefAE3FgkRrQ2qafn4CIL594KaxbTVsb9Lb3PlMMmGGN QD9l7/gs61ad3maO/hmVdIHcx/ICESKu/9Of3ju+wbC8vhT2v2NFAk1VvKdCfDC7jnbq 3iFLnrjyBPS2IT+rNCESR57WYydz0uJ+KiJ02cgJJagWLy9z5B6wouVKODA6Wo6cxXuC 5mpfbeJUJpXbWq5owHIkAb3WL0rCrupk7Ka4cD0CVBWQbe2UiyWwNtxO0C6xZ9XUyxU4 FPuA== X-Gm-Message-State: AOAM5323NSQAatOjQHddoCRqK3H5IbrjDA4iBbhhfi0xQeSV4M7qoFxJ 0uWLlA/LUB7ZX1utbkTtDjQp6Yyvczlg5AGrcP0= X-Google-Smtp-Source: ABdhPJypXJUqkb9XMD3a0SvT52jIELP9jCPcQ4BAURc32XX0X1Pzk8mJQfNEAJ4outmI9yR8+mwfIS/QY1Wbba9mZDw= X-Received: by 2002:a17:906:5052:: with SMTP id e18mr16755490ejk.112.1621728318923; Sat, 22 May 2021 17:05:18 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Trent Piepho Date: Sat, 22 May 2021 17:05:08 -0700 Message-ID: Subject: Re: A divide by zero bug in lib/math/rational.c (with triggering input) To: Andy Shevchenko Cc: Daniel Latypov , Yiyuan guo , "linux-kernel@vger.kernel.org" , "andy@kernel.org" , "akpm@linux-foundation.org" , "oskar@scara.com" Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, May 21, 2021 at 2:53 AM Andy Shevchenko 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.