Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

fractions.Fraction.__pow__ does unneeded renormalization #65335

Closed
Orborde mannequin opened this issue Apr 2, 2014 · 13 comments
Closed

fractions.Fraction.__pow__ does unneeded renormalization #65335

Orborde mannequin opened this issue Apr 2, 2014 · 13 comments
Assignees
@rhettinger
Labels
easy stdlib Python modules in the Lib dir type-bug An unexpected behavior, bug, or error

Comments

@Orborde
Copy link
Mannequin

Orborde mannequin commented Apr 2, 2014

BPO 21136
Nosy @rhettinger, @mdickinson, @ned-deily, @ezio-melotti, @vedgar
Files
  • fraction_pow.diff: Patch Fractions.pow
  • fraction_pow2.diff: Revised patch using _normalize=False
    		•

    Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = 'https://github.com/rhettinger'
closed_at = <Date 2014-04-05.08:30:50.804>
created_at = <Date 2014-04-02.23:52:30.331>
labels = ['easy', 'type-bug', 'library']
title = 'fractions.Fraction.__pow__ does unneeded renormalization'
updated_at = <Date 2016-07-20.19:48:34.542>
user = 'https://bugs.python.org/Orborde'

    bugs.python.org fields:

    activity = <Date 2016-07-20.19:48:34.542>
actor = 'ned.deily'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2014-04-05.08:30:50.804>
closer = 'mark.dickinson'
components = ['Library (Lib)']
creation = <Date 2014-04-02.23:52:30.331>
creator = 'Orborde'
dependencies = []
files = ['34707', '34719']
hgrepos = []
issue_num = 21136
keywords = ['patch', 'easy']
message_count = 13.0
messages = ['215409', '215412', '215428', '215429', '215430', '215431', '215492', '215532', '215584', '215585', '270548', '270890', '270891']
nosy_count = 7.0
nosy_names = ['rhettinger', 'mark.dickinson', 'ned.deily', 'ezio.melotti', 'python-dev', 'Orborde', 'veky']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue21136'
versions = ['Python 3.5']
    @Orborde
    Copy link
    Mannequin Author

    Orborde mannequin commented Apr 2, 2014

    The following Python runs unnecessarily slowly:

    import fractions
fractions.Fraction(6249919, 6250000) ** 89993

    The problem here is that Fraction.__pow__ constructs a new Fraction() to return, and Fraction.__new__ tries to gcd to normalize the numerator/denominator. The gcd is very, very slow, and more to the point, unnecessary; raising a normalized fraction to an integer power will always yield another normalized fraction.

    fractions.Fraction.__pow__ should use this trick to make the code snippet above fast.

    @Orborde Orborde mannequin added performance Performance or resource usage stdlib Python modules in the Lib dir labels Apr 2, 2014
    @rhettinger
    Copy link
    Contributor

    This looks easily doable.

    @rhettinger rhettinger added the easy label Apr 3, 2014
    @rhettinger rhettinger self-assigned this Apr 3, 2014
    @mdickinson
    Copy link
    Member

    LGTM.

    @mdickinson
    Copy link
    Member

    Hmm. Does this work correctly in the case Fraction(0, 1) ** -2?

    @mdickinson
    Copy link
    Member

    Does this work correctly in the case Fraction(0, 1) ** -2?

    Looks like it doesn't. How about adding a _skip_normalization keyword argument to Fraction.__new__ instead? That would ensure that any future changes made to __new__ don't get skipped by this fast path.

    @mdickinson
    Copy link
    Member

    (And other operations like __pos__, __neg__ and __abs__ would benefit from a _skip_normalization flag, too.)

    @rhettinger
    Copy link
    Contributor

    Thanks Mark, that is an excellent suggestion.

    @mdickinson
    Copy link
    Member

    LGTM. (For real this time :-).

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Apr 5, 2014

    New changeset 91d7fadac271 by Mark Dickinson in branch 'default':
    Issue bpo-21136: Avoid unnecessary normalization in Fractions resulting from power and other operations.
    http://hg.python.org/cpython/rev/91d7fadac271

    @mdickinson
    Copy link
    Member

    Applied. I added an extra test for the Fraction(0, 1) ** 2 case.

    @vedgar
    Copy link
    Mannequin

    vedgar mannequin commented Jul 16, 2016

    Unfortunately, this introduced a bug. It seems Mark Dickinson should go easier on his LGTMs. :-)

    >>> import fractions
>>> fractions.Fraction(-1, 2) ** -1
Fraction(2, -1)

    That is a really strange object, since it's not normalized, and many functions expect all Fractions to be. For example,

    >>> _ == -2
False

    Of course, the easy fix would be to change line 52 of fractions.py to _normalize=True - but that would reintroduce the slowness talked about in the original message. Alternative fix would be to be careful about sign of the base, which might be messy if we intend to be completely general -- for example, in finite quotient rings, fractions don't have well-defined signs. [I'm not quite sure why the code in fractions.py is so general, maybe someone really wanted such a level of generality. I don't, so I'd be fine with this working only on int/int Fractions.]

    @vedgar vedgar mannequin added type-bug An unexpected behavior, bug, or error and removed performance Performance or resource usage labels Jul 17, 2016
    @ned-deily
    Copy link
    Member

    @vedran, the original issue is closed and the code for it already released. Please open a new issue referencing this one, otherwise your comments here will likely be forgotten.

    @ned-deily
    Copy link
    Member

    I now see Vedran has already opened bpo-27539 for this. Sorry for the additional noise.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees

    @rhettinger rhettinger

    Labels
    easy stdlib Python modules in the Lib dir type-bug An unexpected behavior, bug, or error
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    3 participants
    @mdickinson @rhettinger @ned-deily