Feature #8796 » bignummulgmp.patch
configure.in (working copy)  

setjmpex.h


)


AC_ARG_WITH([gmp],


[AS_HELP_STRING([withoutgmp],


[disable GNU GMP to accelerate Bignum operations])],


[],


[with_gmp=yes])


AS_IF([test "x$with_gmp" != xno],


[AC_CHECK_HEADERS(gmp.h)


AS_IF([test "x$ac_cv_header_gmp_h" != xno],


AC_CHECK_LIB([gmp], [__gmpz_init]))])


dnl check for large file stuff


mv confdefs.h confdefs1.h


: > confdefs.h

bignum.c (working copy)  

#endif


#include <assert.h>


#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)


#define USE_GMP


#include <gmp.h>


#endif


VALUE rb_cBignum;


const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";


...  ...  
#define KARATSUBA_BALANCED(xn, yn) ((yn)/2 < (xn))


#define TOOM3_BALANCED(xn, yn) (((yn)+2)/3 * 2 < (xn))


#define GMP_MUL_DIGITS 20


#define KARATSUBA_MUL_DIGITS 70


#define TOOM3_MUL_DIGITS 150


...  ...  
return z;


}


#ifdef USE_GMP


static void


bary_mul_gmp(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)


{


const size_t nails = (sizeof(BDIGIT)SIZEOF_BDIGITS)*CHAR_BIT;


mpz_t x, y, z;


size_t count;


assert(xn + yn <= zn);


mpz_inits(x, y, z, 0);


mpz_import(x, xn, 1, sizeof(BDIGIT), 0, nails, xds);


if (xds == yds && xn == yn) {


mpz_mul(z, x, x);


}


else {


mpz_import(y, yn, 1, sizeof(BDIGIT), 0, nails, yds);


mpz_mul(z, x, y);


}


mpz_export (zds, &count, 1, sizeof(BDIGIT), 0, nails, z);


BDIGITS_ZERO(zds+count, zncount);


mpz_clears(x, y, z, 0);


}


VALUE


rb_big_mul_gmp(VALUE x, VALUE y)


{


size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn;


VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));


bary_mul_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);


RB_GC_GUARD(x);


RB_GC_GUARD(y);


return z;


}


#endif


static void


bary_mul1(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)


{


...  ...  
static void


bary_mul(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)


{


#ifdef USE_GMP


const size_t naive_threshold = GMP_MUL_DIGITS;


#else


const size_t naive_threshold = KARATSUBA_MUL_DIGITS;


#endif


if (xn <= yn) {


if (xn < KARATSUBA_MUL_DIGITS) {


if (xn < naive_threshold) {


if (xds == yds && xn == yn)


bary_sq_fast(zds, zn, xds, xn);


else


...  ...  
}


}


else {


if (yn < KARATSUBA_MUL_DIGITS) {


if (yn < naive_threshold) {


bary_mul1(zds, zn, yds, yn, xds, xn);


return;


}


}


#ifdef USE_GMP


bary_mul_gmp(zds, zn, xds, xn, yds, yn);


#else


bary_mul_toom3_start(zds, zn, xds, xn, yds, yn, NULL, 0);


#endif


}


struct big_div_struct {


...  ...  
xds = BDIGITS(x);


zds = BDIGITS(z);


#ifdef USE_GMP


if (xn < GMP_MUL_DIGITS)


bary_sq_fast(zds, zn, xds, xn);


else


bary_mul(zds, zn, xds, xn, xds, xn);


#else


if (xn < KARATSUBA_MUL_DIGITS)


bary_sq_fast(zds, zn, xds, xn);


else


bary_mul(zds, zn, xds, xn, xds, xn);


#endif


RB_GC_GUARD(x);


return z;

ext/test/bignum/mul.c (working copy)  

return rb_big_norm(rb_big_mul_toom3(big(x), big(y)));


}


#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)


static VALUE


mul_gmp(VALUE x, VALUE y)


{


return rb_big_norm(rb_big_mul_gmp(big(x), big(y)));


}


#else


#define mul_gmp rb_f_notimplement


#endif


void


Init_mul(VALUE klass)


{


...  ...  
rb_define_method(rb_cInteger, "big_mul_balance", mul_balance, 1);


rb_define_method(rb_cInteger, "big_mul_karatsuba", mul_karatsuba, 1);


rb_define_method(rb_cInteger, "big_mul_toom3", mul_toom3, 1);


rb_define_method(rb_cInteger, "big_mul_gmp", mul_gmp, 1);


}

internal.h (working copy)  

VALUE rb_big_mul_balance(VALUE x, VALUE y);


VALUE rb_big_mul_karatsuba(VALUE x, VALUE y);


VALUE rb_big_mul_toom3(VALUE x, VALUE y);


#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)


VALUE rb_big_mul_gmp(VALUE x, VALUE y);


#endif


VALUE rb_big_sq_fast(VALUE x);


/* file.c */
