New or modified function

Wojciech Florek Wojciech.Florek at
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