On Thu, Jul 11, 2013 at 5:01 AM, Mateusz Paprocki <[email protected]> wrote:
> Hi, > > On 11 July 2013 11:14, Thilina Rathnayake <[email protected]> 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<https://github.com/sympy/sympy/pull/2168#discussion-diff-4672557>. >> 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 > 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()). > >> 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 >> >> >> On Thu, Jul 11, 2013 at 2:12 PM, Mateusz Paprocki <[email protected]>wrote: >> >>> Hi, >>> >>> On 11 July 2013 10:17, Stephen Loo <[email protected]> wrote: >>> >>>> 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? >>>> >>> >>> 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 [email protected]. >>>> To post to this group, send email to [email protected]. >>>> Visit this group at http://groups.google.com/group/sympy. >>>> For more options, visit https://groups.google.com/groups/opt_out. >>>> >>>> >>>> >>> >>> Mateusz >>> >>> -- >>> 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 [email protected]. >>> To post to this group, send email to [email protected]. >>> Visit this group at http://groups.google.com/group/sympy. >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> -- >> 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 [email protected]. >> To post to this group, send email to [email protected]. >> Visit this group at http://groups.google.com/group/sympy. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > Mateusz > > -- > 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 [email protected]. > To post to this group, send email to [email protected]. > Visit this group at http://groups.google.com/group/sympy. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- 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 [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
