Re: GMP bignum results using double cells.

[Rob Browning]

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