New or modified function

Wojciech Florek Wojciech.Florek at amu.edu.pl
Tue Nov 17 13:50:27 CET 2009

Hi!

I have a very small and not so difficult problem. I can make some
shortcuts or find trivial solutions of it, but I'm not so good in
programming to make changes in mpn-functions or even in mpz-functions.

In GMP there are lcm functions (mpz_lcm and mpz_lcm_ui). I need another
number thoretical function (I call it "exclusive multiplication"),

exmul(a,b)=lcm(a,b)/gcd(a,b)

Using gcd and lcm from GMP gcd(a,b) is calculated twice. So I use
(g=gcd(a,b))
exmul(a,b)=(a/g)*(b/g).
BTW, I wonder if exmul=(a*b)/(g^2) is faster (2 divexact and 1 mul
versus 1 mul, 1 square and 1 divexact, but for larger numbers). As a
rule I need it for a,b>0, but a "signed" version is worth discussing
(i.e. sign(exmul(a,b))=sign(a*b)).

It needs only small modifications in the mpz_lcm code, but I'm affraid
I'll make something stupid (I'm not familiar with all TMP_DECL etc.
staff).  Moreover, I think that this function maybe helpful for other
people.

As a rule I need both: gcd and exmul, so it should be
void exmul(g mpz_ptr, e mpz_ptr, a mpz_srcptr, b mpz_srcptr), where
g may be NULL.
What is the reason? I work with numbers (q,r)=q Sqrt(r) (q in Q or Z,
integer r>0 is square-free). Then we have:
(q,r)*(s,t)=(q*s*g,e),
where g=gcd(r,t), e=exmul(r,t) is square-free for square-free r,t.

Sometimes exmul(a,b) fits unsigned int, so exmul_ui or something similar
may be also useful. E.g. exmul(2*10^500, 3*10^500)=6.

Regards

Wojtek Florek
A. Mickiewicz Univ.
Fac. Physics.