classification
Title: fractions.Fraction.__pow__ does unneeded renormalization
Type: performance 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, python-dev, rhettinger
Priority: normal Keywords: easy, patch

Created on 2014-04-02 23:52 by Orborde, last changed 2014-04-05 08:30 by mark.dickinson. 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 (10)
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.
History
Date User Action Args
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