Hi, On 11 July 2013 12:04, Christophe Bal <[email protected]> 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. > > Christophe BAL > > > 2013/7/11 Mateusz Paprocki <[email protected]> > >> 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(). >>> >>> 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. >> >>> 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. > > > 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.
