fractions.Fraction.__pow__ does unneeded renormalization

[Orborde]

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]

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.

[rhettinger]

This looks easily doable.

[mdickinson]

LGTM.

[mdickinson]

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

[mdickinson]

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]

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

[rhettinger]

Thanks Mark, that is an excellent suggestion.

[mdickinson]

LGTM. (For real this time :-).

[python-dev]

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]

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