New or modified function
Wojciech Florek
Wojciech.Florek at amu.edu.pl
Fri Nov 20 12:53:33 CET 2009
Hi to All of You!!!
Many thanks for responses and interesting discussion. I'm especially
grateful to Paul for the speed test and for keeping me in mind!
Your mails have encouraged me to present my "needs" in more details.
In some problems I deal with a system of (homogeneous!) linear equation
with coefficients q*Sqrt(r); q is rational (multiplying the overall lcm
it can be change to a signed integer) and r>0 is (or can be made)
square-free (0 is codded as 0*Sqrt(1)). Moreover, these coefficients are
so specfic, that multiplying the j-th equation by Sqrt(c_j) (c_j is
square-free, of course) all equations can be written as
\sum_k q_{jk} Sqrt(r_k) x_k = 0
(q_k can be transform to integer usind lcm, and r_k>0 is square-free and
does NOT depend on j). Then substituting y_k= Sqrt(r_k) x_k i obtain
linear equations with INTEGER coefficients, which can be solved very
fast and _exactly_ with GMP Lib. So, you see that the bottle-neck is
rather in solving the system of equations than in transforming
coefficients to integers. Nevertheless, a good function for
multiplication of Sqrt(a)*Sqrt(b)=gcd(a,b)*Sqrt(exmul(a,b)) will be
helpful. At present, numbers c_j and r_k I use are rather small (fitting
(long) unsigned int), so I've written necessary functions using the
standard gcd code (I use mainly the standard Euclid algorithm). In the
next step I'll use what Niels has suggested:
> I think it would be simplest to implement this on top of the mpz
> interface, not messing with internals and things like TMP_DECL.
but basing on mpz_gcd function(s) only. I'm not going to use original
mpz_lcm, since it calculates (invokes) gcd functions, but it uses this
value internally only. So there is my next step: modify mpz_lcm in such
way, that it will return also gcd
mpz_newlcm(mpz_ptr g, mpz_ptr l, mpz_srcptr a, mpz_srcptr b)
(g may be NULL). In this way I don't need to invoke mpz_gcd myself.
However, I still thing that the function, I've called "exclusive
multiplication", can be interested from the point of view of the number
theory (I've used it in some other places, too). Therefore, its
inclusion in the further versions of the (fantastic!) GNU MP Library
seems to be well motivated.
Thanks ones more!!!!!
Wojtek Florek (aka WsF)
More information about the gmp-discuss
mailing list