classification
Title: fractions.Fraction.__pow__ does unneeded renormalization
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Orborde, ezio.melotti, mark.dickinson, ned.deily, python-dev, rhettinger, veky
Priority: normal Keywords: easy, patch

Created on 2014-04-02 23:52 by Orborde, last changed 2016-07-20 19:48 by ned.deily. This issue is now closed.

Files
File name Uploaded Description Edit
fraction_pow.diff rhettinger, 2014-04-03 01:30 Patch Fractions.__pow__ review
fraction_pow2.diff rhettinger, 2014-04-04 06:01 Revised patch using _normalize=False review
Messages (13)
msg215409 - (view) Author: William Ehlhardt (Orborde) Date: 2014-04-02 23:52
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.
msg215412 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-04-03 01:12
This looks easily doable.
msg215428 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-04-03 08:36
LGTM.
msg215429 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-04-03 08:37
Hmm.  Does this work correctly in the case `Fraction(0, 1) ** -2`?
msg215430 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-04-03 08:41
> 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.
msg215431 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-04-03 08:43
(And other operations like `__pos__`, `__neg__` and `__abs__` would benefit from a `_skip_normalization` flag, too.)
msg215492 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-04-04 06:01
Thanks Mark, that is an excellent suggestion.
msg215532 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-04-04 16:16
LGTM.  (For real this time :-).
msg215584 - (view) Author: Roundup Robot (python-dev) Date: 2014-04-05 08:29
New changeset 91d7fadac271 by Mark Dickinson in branch 'default':
Issue #21136: Avoid unnecessary normalization in Fractions resulting from power and other operations.
http://hg.python.org/cpython/rev/91d7fadac271
msg215585 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-04-05 08:30
Applied.  I added an extra test for the `Fraction(0, 1) ** 2` case.
msg270548 - (view) Author: Vedran Čačić (veky) * Date: 2016-07-16 08:46
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.]
msg270890 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2016-07-20 19:22
@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.
msg270891 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2016-07-20 19:48
I now see Vedran has already opened Issue27539 for this.  Sorry for the additional noise.
History
Date User Action Args
2016-07-20 19:48:34ned.deilysetmessages: + msg270891
2016-07-20 19:22:56ned.deilysetnosy: + ned.deily

messages: + msg270890
versions: - Python 3.6
2016-07-17 05:47:17vekysettype: performance -> behavior
2016-07-16 08:46:43vekysetnosy: + veky

messages: + msg270548
versions: + Python 3.6
2014-04-05 08:30:58mark.dickinsonsetstage: needs patch -> resolved
2014-04-05 08:30:50mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg215585
2014-04-05 08:29:16python-devsetnosy: + python-dev
messages: + msg215584
2014-04-04 16:16:22mark.dickinsonsetmessages: + msg215532
2014-04-04 06:01:19rhettingersetfiles: + fraction_pow2.diff

messages: + msg215492
2014-04-03 08:43:11mark.dickinsonsetmessages: + msg215431
2014-04-03 08:41:19mark.dickinsonsetmessages: + msg215430
2014-04-03 08:37:34mark.dickinsonsetmessages: + msg215429
2014-04-03 08:36:32mark.dickinsonsetmessages: + msg215428
2014-04-03 01:30:58rhettingersetfiles: + fraction_pow.diff
keywords: + patch
2014-04-03 01:12:54rhettingersetkeywords: + easy
assignee: rhettinger
messages: + msg215412
2014-04-03 00:08:36ezio.melottisetnosy: + rhettinger, mark.dickinson, ezio.melotti
stage: needs patch

versions: + Python 3.5, - Python 2.7, Python 3.2
2014-04-02 23:52:30Orbordecreate