gcd

[Stephen Loo]

Hi all,

I found that there are many different kind of gcd in sympy different module, such as

sympy.core.numbers.igcd
sympy.polys.polytools.gcd
sympy.polys.polytools.gcdex
sympy.polys.polytools.gcd_list
sympy.polys.polytools.half_gcdex

And the new one
sympy.solvers.diophantine.extended_euclid

They calculate integer gcd or polynomial gcd. I suggest to make single public function call, like gamma, put in integer argument and return integer, put in polynomial argument and return polynomial. And gcd function should not limit to 2 integer only, for example, gcd(10, 15, 20) = 5

Any idea? Any suggestion?

Thanks.

[Mateusz Paprocki]

Hi,

First of all, functions gcdex() and half_gcdex() don't count because they implement extended Euclidean algorithm. I didn't know about extended_euclid(). It seems redundant. igcd() is a specialized function that works only with integers and is needed internally to reduce overhead that gcd() function has. The function you would like to have is gcd(). It works with numbers, polynomials and whatever that has a gcd() method. It either takes two arguments (plus symbols and options in polynomial case) or one iterable (plus symbols and options in polynomial case). The iterable case is equivalent to calling gcd_list() explicitly (that's why there is gcd_list()). Currently it isn't possible to support gcd(1, 2, 3, 4, 5) syntax, because that effectively means (in the current API) compute GCD of 1 and 2 which are polynomials in 3, 4, 5 (treated as symbols) in the default coefficient domain (which is integer ring). In the integer case this limitation could be relaxed easily, but then the API would be inconsistent, because gcd(x, y, z) would still mean GCD of polynomials x and y in z (x*z**0, y*z**0) (over ZZ[x, y]).

 

Thanks.

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

Mateusz

[Thilina Rathnayake]

Hi,

I implemented the extended_euclid() in Diophantine module without knowing that
gcdex() existed. However, Chris pointed out that extended_euclid() is much faster.
Take a look at here. He suggested to rename extended_euclid() to igcdex().

I also feel that when we are dealing with integers, i.e when using igcd() we should
allow inputting more than two numbers at a time. It doesn't break the API, does it?

Regards,
Thilina

[Stephen Loo]

gcdex() handle expression only, no redundant.


Stephen Loo於 2013年7月11日星期四UTC+8下午4時17分45秒寫道：

[Mateusz Paprocki]

Hi,

On 11 July 2013 11:14, Thilina Rathnayake <thilin...@gmail.com> wrote:

Hi,

I implemented the extended_euclid() in Diophantine module without knowing that
gcdex() existed. However, Chris pointed out that extended_euclid() is much faster.
Take a look at here. He suggested to rename extended_euclid() to igcdex().

I also feel that when we are dealing with integers, i.e when using igcd() we should
allow inputting more than two numbers at a time. It doesn't break the API, does it?

gcdex() is a wrapper and works over as many domains as possible, so it has to be slower than a dedicated function. However, it's speed can be improved in the integer case. There is already igcdex() function sympy.core.numbers, so you should be using this if you need extended Euclidean algorithm over integers (strange no one pointed this out earlier, because this function is there since 2008). Also extended_euclid() is recursive (at least in that PR) and igcdex() is iterative.

Mateusz

[Mateusz Paprocki]

Hi,

On 11 July 2013 11:14, Thilina Rathnayake <thilin...@gmail.com> wrote:

Hi,

I implemented the extended_euclid() in Diophantine module without knowing that
gcdex() existed. However, Chris pointed out that extended_euclid() is much faster.
Take a look at here. He suggested to rename extended_euclid() to igcdex().

btw. Even if you don't know if a function exists or if it exists what is it's name, it's not that hard learn it. For example, the following simple query (could be extended to give broader results, if necessary) with git grep gives quite a lot of results:

$ git grep -i "extended\s\+euclid"

sympy/integrals/risch.py:    Extended Euclidean Algorithm, Diophantine version.

sympy/integrals/risch.py:    # Extended Euclidean Algorithm (Diophantine Version) pg. 13

sympy/polys/euclidtools.py:    Half extended Euclidean algorithm in `F[x]`.

sympy/polys/euclidtools.py:    Half extended Euclidean algorithm in `F[X]`.

sympy/polys/euclidtools.py:    Extended Euclidean algorithm in `F[x]`.

sympy/polys/euclidtools.py:    Extended Euclidean algorithm in `F[X]`.

sympy/polys/galoistools.py:    Extended Euclidean Algorithm in ``GF(p)[x]``.

sympy/polys/galoistools.py:    in ``GF(11)[x]``. Application of Extended Euclidean Algorithm gives::

sympy/polys/polyclasses.py:        """Half extended Euclidean algorithm, if univariate. """

sympy/polys/polyclasses.py:        """Extended Euclidean algorithm, if univariate. """

sympy/polys/polytools.py:        Half extended Euclidean algorithm of ``f`` and ``g``.

sympy/polys/polytools.py:        Extended Euclidean algorithm of ``f`` and ``g``.

sympy/polys/polytools.py:    Half extended Euclidean algorithm of ``f`` and ``g``.

sympy/polys/polytools.py:    Extended Euclidean algorithm of ``f`` and ``g``. 

It doesn't give you igcdex() directly, but then you can check those results and learn that the name is gcdex() and either grep again for "def gcdex" or follow implementation tree to igcdex() (gcdex() -> PythonIntegerRing.gcdex() -> igcdex()). 

Mateusz

[Christophe Bal]

Hello,

gcd(a ; b ; c) = gcd(a ; gcd(b ; c)) = gcd(gcd(a ; b) ; c)).

The best ways to compute gcd(a ; b ; c ; d ; e ; ...) should be to first sort the arguments. If we suppose that  a <= b <= c <= d <= e <= ... . Let L be this list of integers. Then you can apply the following steps.

     1)  Compute g = gcd(L[0] ; L[1]). If the result is 1 then nothing else has to be done.

     2)  If L is empty, g is the gcd, else remove L[0] and L[1] and go to 1).

Christophe BAL

2013/7/11 Mateusz Paprocki <mat...@gmail.com>

[Stephen Loo]

Thanks, gcd is more complicated than what I think.

Stephen Loo於 2013年7月11日星期四UTC+8下午4時17分45秒寫道：

[Mateusz Paprocki]

Hi,

On 11 July 2013 12:04, Christophe Bal <proj...@gmail.com> wrote:

Hello,

gcd(a ; b ; c) = gcd(a ; gcd(b ; c)) = gcd(gcd(a ; b) ; c)).

The best ways to compute gcd(a ; b ; c ; d ; e ; ...) should be to first sort the arguments. If we suppose that  a <= b <= c <= d <= e <= ... . Let L be this list of integers. Then you can apply the following steps.

     1)  Compute g = gcd(L[0] ; L[1]). If the result is 1 then nothing else has to be done.

     2)  If L is empty, g is the gcd, else remove L[0] and L[1] and go to 1).

That's an interesting point. This could even work with polynomials.

Mateusz

[Stephen Loo]

2) If L is empty, g is the gcd, else L.pop(0), L[0] = g and goto 1).

Christophe Bal於 2013年7月11日星期四UTC+8下午6時04分19秒寫道：

[Aaron Meurer]

On Thu, Jul 11, 2013 at 5:01 AM, Mateusz Paprocki <mat...@gmail.com> wrote:

Hi,

On 11 July 2013 11:14, Thilina Rathnayake <thilin...@gmail.com> wrote:

Hi,

I implemented the extended_euclid() in Diophantine module without knowing that
gcdex() existed. However, Chris pointed out that extended_euclid() is much faster.
Take a look at here. He suggested to rename extended_euclid() to igcdex().

btw. Even if you don't know if a function exists or if it exists what is it's name, it's not that hard learn it. For example, the following simple query (could be extended to give broader results, if necessary) with git grep gives quite a lot of results:

$ git grep -i "extended\s\+euclid"

sympy/integrals/risch.py:    Extended Euclidean Algorithm, Diophantine version.

sympy/integrals/risch.py:    # Extended Euclidean Algorithm (Diophantine Version) pg. 13

You missed these ones, the diophantine version of gcdex, which currently live in the Risch algorithm, but which should be moved to the polys (and probably a integer versions made).

Aaron Meurer