From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Rob Browning Newsgroups: gmane.lisp.guile.devel Subject: Re: GMP bignum results using double cells. Date: Wed, 26 Feb 2003 19:27:39 -0600 Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: <873cmaseb8.fsf@raven.i.defaultvalue.org> References: <878yw3o8rd.fsf@raven.i.defaultvalue.org> <87vfz6wvw1.fsf@zip.com.au> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1046309330 11865 80.91.224.249 (27 Feb 2003 01:28:50 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Thu, 27 Feb 2003 01:28:50 +0000 (UTC) Cc: guile-devel@gnu.org Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 18oCqt-000358-00 for ; Thu, 27 Feb 2003 02:28:48 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18oCqg-00080Y-01 for guile-devel@m.gmane.org; Wed, 26 Feb 2003 20:28:34 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18oCqN-0007yr-00 for guile-devel@gnu.org; Wed, 26 Feb 2003 20:28:15 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18oCqL-0007yS-00 for guile-devel@gnu.org; Wed, 26 Feb 2003 20:28:14 -0500 Original-Received: from dsl093-098-016.wdc1.dsl.speakeasy.net ([66.93.98.16] helo=defaultvalue.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18oCpy-0007p3-00 for guile-devel@gnu.org; Wed, 26 Feb 2003 20:27:50 -0500 Original-Received: from raven.i.defaultvalue.org (raven.i.defaultvalue.org [192.168.1.7]) by defaultvalue.org (Postfix) with ESMTP id E962F1E8; Wed, 26 Feb 2003 19:27:39 -0600 (CST) Original-Received: by raven.i.defaultvalue.org (Postfix, from userid 1000) id E6947D1859; Wed, 26 Feb 2003 19:27:39 -0600 (CST) Original-To: Kevin Ryde In-Reply-To: <87vfz6wvw1.fsf@zip.com.au> (Kevin Ryde's message of "Thu, 27 Feb 2003 07:54:22 +1000") User-Agent: Gnus/5.090008 (Oort Gnus v0.08) Emacs/21.2 (i386-pc-linux-gnu) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:1986 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:1986 Kevin Ryde writes: > Rob Browning writes: >> >> ("bench-random-op gcd" "./guile-1.7" ((user . 276) (sys . 0) (gc . 59))) >> ("bench-random-op gcd" "./guile-gmp" ((user . 312) (sys . 0) (gc . 33))) > > Is that with mpz_gcd? From nosing around the existing scm_gcd I might > have thought mpz_gcd would be faster. Here's what I get currently: starting trials ("bench-random-op +" "./guile-gmp" ((user . 294) (sys . 0) (gc . 30))) ("bench-random-op -" "./guile-gmp" ((user . 289) (sys . 0) (gc . 31))) ("bench-random-op *" "./guile-gmp" ((user . 307) (sys . 1) (gc . 29))) ("bench-random-op /" "./guile-gmp" ((user . 316) (sys . 0) (gc . 30))) ("bench-random-op gcd" "./guile-gmp" ((user . 302) (sys . 0) (gc . 31))) ("bench-random-op lcm" "./guile-gmp" ((user . 345) (sys . 0) (gc . 31))) To compare gcd in current 1.7 still looks like this: ("bench-random-op gcd" "./guile-1.7" ((user . 253) (sys . 0) (gc . 55))) The fact that all the values are so close makes me wonder if much of the cost is just interpreter related. FWIW below is the current gcd_implementation -- I believe the only clause being executed in the test above is the 2 bigs clause that I just marked with /* big big clause */ below -- feel free to critique. Note that I left the same algorithm as before for the inum case. SCM_GPROC1 (s_gcd, "gcd", scm_tc7_asubr, scm_gcd, g_gcd); /* "Return the greatest common divisor of all arguments.\n" * "If called without arguments, 0 is returned." */ SCM scm_gcd (SCM x, SCM y) { if (SCM_UNBNDP (y)) { if (SCM_UNBNDP (x)) { return SCM_INUM0; } else { return x; } } if (SCM_INUMP (x)) { if (SCM_INUMP (y)) { long xx = SCM_INUM (x); long yy = SCM_INUM (y); long u = xx < 0 ? -xx : xx; long v = yy < 0 ? -yy : yy; long result; if (xx == 0) { result = v; } else if (yy == 0) { result = u; } else { long k = 1; long t; /* Determine a common factor 2^k */ while (!(1 & (u | v))) { k <<= 1; u >>= 1; v >>= 1; } /* Now, any factor 2^n can be eliminated */ if (u & 1) { t = -v; } else { t = u; b3: t = SCM_SRS (t, 1); } if (!(1 & t)) goto b3; if (t > 0) u = t; else v = -t; t = u - v; if (t != 0) goto b3; result = u * k; } if (SCM_POSFIXABLE (result)) { return SCM_MAKINUM (result); } else { return scm_i_long2big (result); } } else if (SCM_BIGP (y)) { SCM result = scm_i_mkbig (); SCM mx = scm_i_mkbig (); mpz_set_si(SCM_I_BIG_MPZ (mx), SCM_INUM (x)); scm_remember_upto_here_1 (x); mpz_gcd(SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (mx), SCM_I_BIG_MPZ (y)); scm_remember_upto_here_2(mx, y); return scm_i_normbig (result); } else { SCM_WTA_DISPATCH_2 (g_gcd, x, y, SCM_ARG2, s_gcd); } } else if (SCM_BIGP (x)) { SCM result = scm_i_mkbig (); if (SCM_INUMP (y)) { SCM my = scm_i_mkbig (); mpz_set_si (SCM_I_BIG_MPZ (my), SCM_INUM (y)); mpz_gcd(SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (x), SCM_I_BIG_MPZ (my)); scm_remember_upto_here_1 (my); } else if (SCM_BIGP (y)) { /* big big clause */ mpz_gcd(SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (x), SCM_I_BIG_MPZ (y)); } else { SCM_WTA_DISPATCH_2 (g_gcd, x, y, SCM_ARG2, s_gcd); } scm_remember_upto_here_2(x, y); return scm_i_normbig (result); } else { SCM_WTA_DISPATCH_2 (g_gcd, x, y, SCM_ARG1, s_gcd); } } -- Rob Browning rlb @defaultvalue.org, @linuxdevel.com, and @debian.org Previously @cs.utexas.edu GPG starting 2002-11-03 = 14DD 432F AE39 534D B592 F9A0 25C8 D377 8C7E 73A4 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel