From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Drew Adams" Newsgroups: gmane.emacs.devel Subject: RE: Elisp manual, node "Comparison of Numbers" Date: Mon, 29 May 2006 11:14:50 -0700 Message-ID: References: <447AF9B8.2080801@student.lu.se> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Trace: sea.gmane.org 1148926539 25517 80.91.229.2 (29 May 2006 18:15:39 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Mon, 29 May 2006 18:15:39 +0000 (UTC) Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon May 29 20:15:34 2006 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1FkmGx-0005rE-U2 for ged-emacs-devel@m.gmane.org; Mon, 29 May 2006 20:15:24 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FkmGw-0002Xa-Rc for ged-emacs-devel@m.gmane.org; Mon, 29 May 2006 14:15:23 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1FkmGg-0002X3-W2 for emacs-devel@gnu.org; Mon, 29 May 2006 14:15:07 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1FkmGf-0002Vq-RX for emacs-devel@gnu.org; Mon, 29 May 2006 14:15:06 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FkmGf-0002Vl-LP for emacs-devel@gnu.org; Mon, 29 May 2006 14:15:05 -0400 Original-Received: from [148.87.113.118] (helo=rgminet01.oracle.com) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_3DES_EDE_CBC_SHA:24) (Exim 4.52) id 1FkmMH-00085j-Ss for emacs-devel@gnu.org; Mon, 29 May 2006 14:20:54 -0400 Original-Received: from rgmsgw300.us.oracle.com (rgmsgw300.us.oracle.com [138.1.186.49]) by rgminet01.oracle.com (Switch-3.1.6/Switch-3.1.6) with ESMTP id k4TIF1G2028714 for ; Mon, 29 May 2006 12:15:01 -0600 Original-Received: from dradamslap (dhcp-amer-whq-csvpn-gw3-141-144-81-124.vpn.oracle.com [141.144.81.124]) by rgmsgw300.us.oracle.com (Switch-3.1.7/Switch-3.1.7) with SMTP id k4TIF0UP020643 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO) for ; Mon, 29 May 2006 12:15:01 -0600 Original-To: "Emacs-Devel" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.6604 (9.0.2911.0) In-Reply-To: <447AF9B8.2080801@student.lu.se> Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1807 X-Brightmail-Tracker: AAAAAQAAAAI= X-Brightmail-Tracker: AAAAAQAAAAI= X-Whitelist: TRUE X-Whitelist: TRUE X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:55439 Archived-At: > (defun approx-equal (x y &optional fuzz) > (setq fuzz (or fuzz 1.0e-8)) > (cond ((= x 0.0) (< y fuzz)) > ((= y 0.0) (< x fuzz)) > (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz)))) Leonard> Looks reasonable, but you have to use (< (abs y) fuzz) etc. Right - forgot the abs. Thx. David> The problem here is that fuzz is a _relative_ measure of equality, and you employ it as an absolute measure here. FUZZ is a relative measure in the final clause and an absolute measure in the first two clauses. Anyway, you are right that my definition mixes absolute with relative measures. It would also be right to say that the same fuzz factor might not always be useful as both an absolute measure and a relative measure this way. My point was that the relative measure given is useless as a measure of proximity to zero. Or, as you echoed it, "Relative measures don't work when comparing with 0." The difference from zero compared to the maximum is always exactly 1.0. By that relative measure, neither 1,000,000,000 nor 0.0000000001 is approximately zero - they fail equality to the same degree (Animal Farm, revisited), as do all other floating-point numbers (except 0.0, which causes division by zero unless treated as a special case). Neither absolute nor relative measure is appropriate in all cases - there is no general comparison algorithm that is good all of the time (duh). Some applications use absolute comparison (which has the drawback of being relatively different comparing small numbers from comparing large numbers); others use relative comparison (sacrificing approximate equality with zero); still others use some combination of the two. And of course approximate equality (by most definitions) is not transitive, whether measured absolutely or relatively. One article I came across put it this way: "Depending on how you came up with the numbers, you may have 1.0 not being approximately equal to 0.999999, or you may have 1.0 being approximately equal to 0.0." Here's a definition I came across that combines absolute and relative comparisons in a way that is better than what I proposed. (I added the defaults for the fuzz factors.) (defun approx-equal (x y &optional rfuzz afuzz) "Return non-nil if numbers X and Y are approximately equal. RFUZZ is a relative fuzz factor. AFUZZ is an absolute fuzz factor. RFUZZ defaults to 1.0e-8. AFUZZ defaults to (/ RFUZZ 10). The algorithm is: (< (abs (- X Y)) (+ AFUZZ (* RFUZZ (+ (abs X) (abs Y)))))." (setq rfuzz (or rfuzz 1.0e-8) afuzz (or afuzz (/ rfuzz 10))) (< (abs (- x y)) (+ afuzz (* rfuzz (+ (abs x) (abs y)))))) This is more flexible than both the definition I gave and the one in the manual. You can of course still shoot yourself in the foot with this, depending on the values you are testing and your choice of fuzz factors. In my application this definition works well, as does the code I sent originally: an absolute test against zero is in fact what I need. Wrt the Elisp manual, I'd suggest 1) going with the original example, 2) pointing out that it does not work for testing approximation to zero, and 3) mentioning that an absolute test can sometimes be appropriate in that case. FYI - These articles are interesting on testing floating-point approximate equality: http://docs.sun.com/source/806-3568/ncg_goldberg.html, http://www.visoracle.com/squeakfaq/float-precision.html. Knuth's Art of Computer Programming vol 2 has a section on this which is also interesting.