Repository navigation
fractions.Fraction.__pow__ does unneeded renormalization #65335
Description
| BPO | 21136 |
|---|---|
| Nosy | @rhettinger, @mdickinson, @ned-deily, @ezio-melotti, @vedgar |
| Files |
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
Orborde commentedon Apr 2, 2014
The following Python runs unnecessarily slowly:
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.
rhettinger commentedon Apr 3, 2014
This looks easily doable.
mdickinson commentedon Apr 3, 2014
LGTM.
mdickinson commentedon Apr 3, 2014
Hmm. Does this work correctly in the case
Fraction(0, 1) ** -2?mdickinson commentedon Apr 3, 2014
Looks like it doesn't. How about adding a
_skip_normalizationkeyword argument toFraction.__new__instead? That would ensure that any future changes made to__new__don't get skipped by this fast path.mdickinson commentedon Apr 3, 2014
(And other operations like
__pos__,__neg__and__abs__would benefit from a_skip_normalizationflag, too.)rhettinger commentedon Apr 4, 2014
Thanks Mark, that is an excellent suggestion.
mdickinson commentedon Apr 4, 2014
LGTM. (For real this time :-).
python-dev commentedon 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 commentedon Apr 5, 2014
Applied. I added an extra test for the
Fraction(0, 1) ** 2case.vedgar commentedon Jul 16, 2016
Unfortunately, this introduced a bug. It seems Mark Dickinson should go easier on his LGTMs. :-)
That is a really strange object, since it's not normalized, and many functions expect all Fractions to be. For example,
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.]
ned-deily commentedon Jul 20, 2016
@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 commentedon Jul 20, 2016
I now see Vedran has already opened bpo-27539 for this. Sorry for the additional noise.