#32314 closed defect (fixed)

passing a generator to gcd() fails

Reported by: Lorenz Panny Owned by:
Priority: minor Milestone: sage-9.5
Component: basic arithmetic Keywords: gcd, generator, list
Cc: Merged in:
Authors: Lorenz Panny Reviewers: Kwankyu Lee
Report Upstream: N/A Work issues:
Branch: e6a3c5d (Commits, GitHub, GitLab) Commit: e6a3c5dfeca8e37ce61efe25dbb3473475ba912c
Dependencies: Stopgaps:

Status badges

Description (last modified by Lorenz Panny)

The following use of gcd() fails:

sage: gcd(x for x in [123,456,789])
# ...
TypeError: object of type 'generator' has no len()

At the same time, lcm() works fine with generators:

sage: lcm(x for x in [123,456,789])
4917048

The proposed fix is to make sure we consume the generator only once in gcd() and pass it to GCD_list() as a list.

Change History (12)

comment:1 Changed 14 months ago by Lorenz Panny

Status: newneeds_review

comment:2 Changed 14 months ago by Kwankyu Lee

It seems this

     if seq.universe() is ZZ:
-        return GCD_list(a)
+        return GCD_list(seq)
     else:
         return __GCD_sequence(seq, **kwargs)

is enough to fix the bug, and enforcing the type in GCD_list() is not necessary. Is it?

comment:3 Changed 14 months ago by Lorenz Panny

You're right. I moved the list cast in GCD_list to an earlier time because GCD_list was also failing on generators due to the len() call, but that could be considered intended. I can change it back if you prefer (I agree that there might be a tiny performance impact in some cases, like when you pass a massive tuple full of Integers).

comment:4 in reply to:  3 Changed 14 months ago by Kwankyu Lee

Replying to lorenz:

I can change it back if you prefer (I agree that there might be a tiny performance impact in some cases, like when you pass a massive tuple full of Integers).

I prefer it because of the performance degradation.

comment:5 Changed 14 months ago by git

Commit: 231862dc186b620cf0f00f7397cf0141b455d682e6a3c5dfeca8e37ce61efe25dbb3473475ba912c

Branch pushed to git repo; I updated commit sha1. New commits:

e6a3c5dundo earlier list cast in GCD_list

comment:6 Changed 14 months ago by Lorenz Panny

Done.

comment:7 Changed 14 months ago by Lorenz Panny

Description: modified (diff)

comment:8 Changed 14 months ago by Kwankyu Lee

Reviewers: Kwankyu Lee
Status: needs_reviewpositive_review

LGTM

comment:9 Changed 14 months ago by Frédéric Chapoton

what about the necessary new doctest ?

comment:10 in reply to:  9 Changed 14 months ago by Kwankyu Lee

Replying to chapoton:

what about the necessary new doctest ?

Feel free to set it back to needs work if you think a doctest is required.

comment:11 Changed 14 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:12 Changed 12 months ago by Volker Braun

Branch: public/fix_gcd_on_generatorse6a3c5dfeca8e37ce61efe25dbb3473475ba912c
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.