[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: GMP bignum results using double cells.
From: |
Rob Browning |
Subject: |
Re: GMP bignum results using double cells. |
Date: |
Wed, 26 Feb 2003 19:27:39 -0600 |
User-agent: |
Gnus/5.090008 (Oort Gnus v0.08) Emacs/21.2 (i386-pc-linux-gnu) |
Kevin Ryde <address@hidden> writes:
> Rob Browning <address@hidden> 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