Improved algorithms for mpq_class multiply/divide with (un)signed long integers
Douglas Boffey
dougaboffey at netscape.net
Wed Oct 14 02:38:38 CEST 2009
Sirs,
I have rewritten the class members (see the attached patch file) for:
static void__gmp_binary_multiplies::eval(mpq_ptr, mpq_srcptr, unsigned long int)
static void__gmp_binary_multiplies::eval(mpq_ptr, unsigned long int, mpq_srcptr)
static void__gmp_binary_multiplies::eval(mpq_ptr, mpq_srcptr, signed long int)
static void__gmp_binary_multiplies::eval(mpq_ptr, signed long int, mpq_srcptr)
static void__gmp_binary_divides::eval(mpq_ptr, mpq_srcptr, unsigned long int)
static void__gmp_binary_divides::eval(mpq_ptr, unsigned long int, mpq_srcptr)
static void__gmp_binary_divides::eval(mpq_ptr, mpq_srcptr, signed long int)
static void__gmp_binary_divides::eval(mpq_ptr, signed long int, mpq_srcptr)
In each case, the mp operations involved (apart from trivial sign changes, etc.) are:
one gcd (N x 1)
one integer div-exact (N x 1)
one integer multiply (N x 1)
instead of:
one gcd (M x N) for canonicalising
one integer multiply (N x 1), although only implicitly x 1 (I don't know whether there are any performance improvements of a _ui() over a non-_ui() function with a single limb in one argument.
Also, no temporaries are created.
Yours,
Douglas Boffey
p.s. I would be interested whether my patch is of any use or not.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gmpxx.h.patch
Type: text/x-patch
Size: 5202 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20091013/0d119c37/attachment.bin>
More information about the gmp-devel
mailing list