| 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) *  |
Date: 2014-04-03 01:12 |
| This looks easily doable. |
|
|
| msg215428 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2014-04-03 08:36 |
| LGTM. |
|
|
| msg215429 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
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) * |
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) * |
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) * |
Date: 2014-04-04 06:01 |
| Thanks Mark, that is an excellent suggestion. |
|
|
| msg215532 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
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) * |
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) * |
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) * |
Date: 2016-07-20 19:48 |
| I now see Vedran has already opened Issue27539 for this. Sorry for the additional noise. |
|
|