Skip to content

fractions.Fraction.__pow__ does unneeded renormalization #65335

Closed
Closed
fractions.Fraction.__pow__ does unneeded renormalization#65335
Assignees
rhettinger
Labels
easystdlibStandard Library Python modules in the Lib/ directorytype-bugAn unexpected behavior, bug, or error

Description

@Orborde
Orborde
mannequin
opened on 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']

    Activity

    1. Orborde commented on Apr 2, 2014

      @Orborde
      Orbordemannequin
      on Apr 2, 2014
      MannequinAuthor

      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.

    2. Orborde
      added
      performancePerformance or resource usage
      stdlibStandard Library Python modules in the Lib/ directory
      on Apr 2, 2014

    3. rhettinger commented on Apr 3, 2014

      @rhettinger
      rhettinger
      on Apr 3, 2014
      Contributor

      This looks easily doable.

    4. rhettinger
      added
      easy
      on Apr 3, 2014
    5. rhettinger
      self-assigned this
      on Apr 3, 2014

    6. mdickinson commented on Apr 3, 2014

      @mdickinson
      mdickinson
      on Apr 3, 2014
      Member

      LGTM.

    7. mdickinson commented on Apr 3, 2014

      @mdickinson
      mdickinson
      on Apr 3, 2014
      Member

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

    8. mdickinson commented on Apr 3, 2014

      @mdickinson
      mdickinson
      on Apr 3, 2014
      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.

    9. mdickinson commented on Apr 3, 2014

      @mdickinson
      mdickinson
      on Apr 3, 2014
      Member

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

    10. rhettinger commented on Apr 4, 2014

      @rhettinger
      rhettinger
      on Apr 4, 2014
      Contributor

      Thanks Mark, that is an excellent suggestion.

    11. mdickinson commented on Apr 4, 2014

      @mdickinson
      mdickinson
      on Apr 4, 2014
      Member

      LGTM. (For real this time :-).

    12. python-dev commented on Apr 5, 2014

      @python-dev
      python-devmannequin
      on Apr 5, 2014
      Mannequin

      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

    13. mdickinson commented on Apr 5, 2014

      @mdickinson
      mdickinson
      on Apr 5, 2014
      Member

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

    14. mdickinson
      closed this as completedon Apr 5, 2014

    15. vedgar commented on Jul 16, 2016

      @vedgar
      vedgarmannequin
      on Jul 16, 2016
      Mannequin

      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.]

    16. vedgar
      added
      type-bugAn unexpected behavior, bug, or error
      and removed
      performancePerformance or resource usage
      on Jul 17, 2016

    17. ned-deily commented on Jul 20, 2016

      @ned-deily
      ned-deily
      on Jul 20, 2016
      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.

    18. ned-deily commented on Jul 20, 2016

      @ned-deily
      ned-deily
      on Jul 20, 2016
      Member

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

    19. ezio-melotti
      transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    Labels

    easystdlibStandard Library Python modules in the Lib/ directorytype-bugAn unexpected behavior, bug, or error

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions