# [GiNaC-list] [PATCH] small improvements of gcd and collect_common_factors

Sheplyakov Alexei varg at theor.jinr.ru
Thu Jun 30 07:49:12 CEST 2005

```Hello!

collect_common_factors does not work with powers, e.g. (in ginsh)

> collect_common_factors((a*x+a*y)^2);
(a*x+a*y)^2

I don't like such a behaviour, so I made the patch.

With that patch, the above code actually works:

> collect_common_factors((a*x+a*y)^2);
a^2*(y+x)^2

To guarantee mathematical correctness, this transformation is applied to
polynomial expressions only:
> collect_common_factors((a*x+a*y)^n);
(a*x+a*y)^n

Apart from collect_common_factors hack, this patch somewhat
improves worst-case performance of gcd and sr_gcd.

Best regards,
Alexei

--
ROOT: an octopus made by nailing extra legs onto a cat.

-------------- next part --------------
Index: normal.cpp
===================================================================
RCS file: /home/cvs/GiNaC/ginac/normal.cpp,v
retrieving revision 1.94.2.6
diff -r1.94.2.6 normal.cpp
716a717,743
> 	if (is_exactly_a<power>(b)) {
> 		const ex& bb(b.op(0));
> 		ex qbar = a;
> 		int exp_b = ex_to<numeric>(b.op(1)).to_int();
> 		for (int i=exp_b; i>0; i--)
> 		{
> 			if (!divide_in_z(qbar, bb, q, var))
> 				return false;
> 			qbar = q;
> 		}
> 		return true;
> 	}
>
> 	if (is_exactly_a<mul>(b)) {
> 		ex qbar = a;
> 		for (const_iterator itrb = b.begin(); itrb != b.end(); ++itrb)
> 		{
> 			sym_desc_vec sym_stats;
> 			get_symbol_stats(a, *itrb, sym_stats);
> 			if (!divide_in_z(qbar, *itrb, q, sym_stats.begin()))
> 				return false;
>
> 			qbar = q;
> 		}
> 		return true;
> 	}
>
1480a1508,1527
> 	if (is_a<symbol>(aex)) {
> 		if (! bex.subs(aex==_ex0, subs_options::no_pattern).is_zero()) {
> 			if (ca)
> 				*ca = a;
> 			if (cb)
> 				*cb = b;
> 			return _ex1;
> 		}
> 	}
>
> 	if (is_a<symbol>(bex)) {
> 		if (! aex.subs(bex==_ex0, subs_options::no_pattern).is_zero()) {
> 			if (ca)
> 				*ca = a;
> 			if (cb)
> 				*cb = b;
> 			return _ex1;
> 		}
> 	}
>
2462,2463c2509,2518
<
< 		return e.to_polynomial(repl);
---
> 		const ex e_exp(e.op(1));
> 		if (e_exp.info(info_flags::posint)) {
> 			ex eb = e.op(0).to_polynomial(repl);
> 			ex factor_local(_ex1);
> 			ex pre_res = find_common_factor(eb, factor_local, repl);
> 			factor *= power(factor_local, e_exp);
> 			return power(pre_res, e_exp);
>
> 		} else
> 			return e.to_polynomial(repl);
2474c2529
< 	if (is_exactly_a<add>(e) || is_exactly_a<mul>(e)) {
---
> 	if (is_exactly_a<add>(e) || is_exactly_a<mul>(e) || is_exactly_a<power>(e)) {
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-list/attachments/20050630/092da310/attachment.pgp
```