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 <matt...@gmail.com>
> Hi,
>
> On 11 July 2013 11:14, Thilina Rathnayake <thilina.r...@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<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 <matt...@gmail.com>wrote:
>>
>>> Hi,
>>>
>>> On 11 July 2013 10:17, Stephen Loo <hingk...@gmail.com> 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 sympy+unsubscr...@googlegroups.com.
>>>> To post to this group, send email to sympy@googlegroups.com.
>>>> 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 sympy+unsubscr...@googlegroups.com.
>>> To post to this group, send email to sympy@googlegroups.com.
>>> 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 sympy+unsubscr...@googlegroups.com.
>> To post to this group, send email to sympy@googlegroups.com.
>> 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 sympy+unsubscr...@googlegroups.com.
> To post to this group, send email to sympy@googlegroups.com.
> 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 sympy+unsubscr...@googlegroups.com.
To post to this group, send email to sympy@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.
For more options, visit https://groups.google.com/groups/opt_out.
