From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Carl Witty Newsgroups: gmane.lisp.guile.devel Subject: Re: scm_i_fraction_reduce thread safety Date: 11 Dec 2003 11:19:02 -0800 Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: <1071170342.1217.60.camel@flare> References: <3FD85844.3060108@ccrma> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: sea.gmane.org 1071171494 1990 80.91.224.253 (11 Dec 2003 19:38:14 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Thu, 11 Dec 2003 19:38:14 +0000 (UTC) Cc: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Dec 11 20:38:09 2003 Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1AUWdV-0001MV-00 for ; Thu, 11 Dec 2003 20:38:09 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AUXa4-0007NS-LL for guile-devel@m.gmane.org; Thu, 11 Dec 2003 15:38:40 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1AUXY1-0005v3-9u for guile-devel@gnu.org; Thu, 11 Dec 2003 15:36:33 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1AUXWu-000468-7s for guile-devel@gnu.org; Thu, 11 Dec 2003 15:35:55 -0500 Original-Received: from [216.254.46.113] (helo=gemini.newtonlabs.com) by monty-python.gnu.org with esmtp (TLSv1:DES-CBC3-SHA:168) (Exim 4.24) id 1AUXWa-0003aj-1u for guile-devel@gnu.org; Thu, 11 Dec 2003 15:35:04 -0500 Original-Received: from flare.newtonlabs.com (flare.newtonlabs.com [10.0.0.13]) by gemini.newtonlabs.com (8.12.3/8.12.3/Debian-6.6) with ESMTP id hBBJXGXT027771; Thu, 11 Dec 2003 11:33:17 -0800 Original-To: Bill Schottstaedt In-Reply-To: <3FD85844.3060108@ccrma> X-Mailer: Ximian Evolution 1.4.3 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:3116 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:3116 On Thu, 2003-12-11 at 03:43, Bill Schottstaedt wrote: > On the need for reduction, I wonder how much of that > notoriety is due to Knuth -- his discussion of this > was in a slightly artificial context, and I've been > intending for a long time to check some "real-world" > situation. (I think it's less of a problem than > calling gcd all the time). I don't have any data on this (merely uninformed opinions), but I'd be nervous about not reducing fractions. If you always reduce, I think that multiplies the cost of operations by about log(n) (where n is the number of bits in the numerator or denominator) (assuming you use Euclid's gcd algorithm, instead of something asymptotically faster). On the other hand, if somebody has an algorithm that builds up fractions which are almost always reducible, then not reducing can make the algorithm slower by an arbitrary amount. For instance, I recently had a problem of coming up with a simple formula (to find the volume of an n-dimensional simplex, if you're curious), where part of the problem was to compute (1/2)*(2/3)*(3/4)*(4/5)*...*(n/(n+1)). When you're working out the formula, it's easy to recognize that this is 1/(n+1). But if I had just wanted a few answers, rather than a general formula, I might have written a little program and ended up with fractions of the form n!/(n+1)!, which would be highly inefficient to work with for large n. I think that one way to avoid arbitrarily-bad behavior is to reduce only if the numerator or denominator is "sufficiently large" (I think this is at most a constant factor worse than always reducing). For instance, we could reduce fractions only if the numerator or denominator is a bignum, in hopes that we will get back to fixnum-sized numbers. Carl Witty _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel