From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Matt Armstrong Newsgroups: gmane.emacs.bugs Subject: bug#58929: 29.0.50; Calc: finding roots utpn doesn't work as advertised Date: Sat, 05 Nov 2022 12:29:10 -0700 Message-ID: <878rkpci9l.fsf@rfc20.org> References: <8773828B-3A5F-4B15-8786-91F6FCB6D2E2@acm.org> <87k04es5bt.fsf@rfc20.org> <83a6588kol.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="22555"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 58929@debbugs.gnu.org To: Eli Zaretskii , Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Nov 05 20:30:23 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1orOs2-0005he-2F for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 05 Nov 2022 20:30:22 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1orOrl-0001rG-Bx; Sat, 05 Nov 2022 15:30:05 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1orOrj-0001qW-JC for bug-gnu-emacs@gnu.org; Sat, 05 Nov 2022 15:30:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1orOrj-0000Ml-1h for bug-gnu-emacs@gnu.org; Sat, 05 Nov 2022 15:30:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1orOri-0005ye-5A for bug-gnu-emacs@gnu.org; Sat, 05 Nov 2022 15:30:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Matt Armstrong Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 05 Nov 2022 19:30:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58929 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 58929-submit@debbugs.gnu.org id=B58929.166767656822916 (code B ref 58929); Sat, 05 Nov 2022 19:30:01 +0000 Original-Received: (at 58929) by debbugs.gnu.org; 5 Nov 2022 19:29:28 +0000 Original-Received: from localhost ([127.0.0.1]:58089 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1orOr7-0005xV-I5 for submit@debbugs.gnu.org; Sat, 05 Nov 2022 15:29:28 -0400 Original-Received: from relay7-d.mail.gandi.net ([217.70.183.200]:56631) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1orOr2-0005xE-E4 for 58929@debbugs.gnu.org; Sat, 05 Nov 2022 15:29:23 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 2168820004; Sat, 5 Nov 2022 19:29:12 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1667676554; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=iN37Y3UB4CqKgDh04h4PIpLlwmKJsahGuqffc25ef0c=; b=il1Wj/JDPjIlBHsXKssXdMfpOAxtRAls+ld6WVUZHQSK8I09MdrxRD/CKgblckKiMSxc6Y 1Mzdaxmm3oUWGFRwiKVufpiyx4zXe4aYDrk33BlTZ/KUgBm35F2QRibacCNfGfKlJQTFZc OeNWygE9sGHkJSrHWUP7WTE/jqqbQHgOBk3+vMBQ2LZK6n5GBpLLTFW4Z5cwCgL7Z7w+gB V3YovRVipOvVXATZNSjkdjMOFWFVf0rAEMNjpEQ3APg4HnTcMjReZsLVX6n+RprPcw08at rb/5Z6IILWFuLwuy2Q2dWkfnTiUb3pc+s5xnC+1e+Y/Z6GsMGXnYDB2TUQofyA== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1orOqs-000E9o-2t; Sat, 05 Nov 2022 12:29:10 -0700 In-Reply-To: <83a6588kol.fsf@gnu.org> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: "bug-gnu-emacs" Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:247155 Archived-At: Eli Zaretskii writes: >> Cc: 58929@debbugs.gnu.org >> From: Mattias Engdeg=C3=A5rd >> Date: Thu, 3 Nov 2022 09:53:02 +0100 >>=20 >> Of course an actual numerical analyst would know immediately what to do.= Is there one in the audience? > > I have good experience from using this technique: > > https://www.researchgate.net/publication/226830173_On_the_Structure_of_= Zero_Finders > > It employs a hybrid method that doesn't need derivatives (but is > almost as fast as Newton). However, its main advantage (which is a > huge one in some real-life situations) is that the structure of the > algorithm allows the caller to make arbitrary modifications to the > approximations that the algorithm produces, and in general have > complete control on the iterations' process. In particular, one can > easily deal with situations where the root approximation goes out of > the expected range, or lands in the area where the function doesn't > behave well enough. Interesting. I like how that algorithm attempts to "do its best" when given a single guess point, then adapts to bisection if it happens to find an opportunity and need. Calc's manual suggests that its "root" function attempts to do the same, opening a window to use this other approach. I'm not sure how to expose the root finding "loop" in calc's UI, but exposing it calc's lisp level interface would be a natural thing to do. https://en.wikipedia.org/wiki/ITP_method also looks like an interesting twist on the bisection/secant method. I have no personal experience with it, and on Wikipedia I always wonder if pages like this are reflective of a true utility or merely the ambitions of the paper's authors! This function needs function values that are opposite in sign before it is useful. It might be possible to incorporate it into the approach Eli linked to, but that method claims to be almost as fast as Newton's method in most cases so it may not need the improvement. I arrived here because I wanted to use calc to compute 95th and 99th percentile confidence intervals of some benchmarking results using the Student's t-distribution. I have figured this out now, but it has been more difficult than I anticipated, and the manual's over-promise with respect to "find the root, any guess works" sent me on a long tangent trying to figure out what I had done wrong. That said, my background in this area is weak, so I don't think I am the right person to improve Emacs' root finding implementation. The patch I sent previously, with my (hopefully) useful suggestions in the user manual, is probably the end of my useful contribution here.