classification
Title: negative Fraction ** negative int not normalized
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.6, Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: mark.dickinson, python-dev, rhettinger, serhiy.storchaka, terry.reedy, veky
Priority: high Keywords: patch

Created on 2016-07-17 07:32 by veky, last changed 2016-08-22 09:57 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
TwCVpiFp.diff veky, 2016-07-19 04:31
issue_27539_fix.patch mark.dickinson, 2016-08-21 08:47 review
Messages (16)
msg270616 - (view) Author: Vedran Čačić (veky) * Date: 2016-07-17 07:32
I already wrote http://bugs.python.org/msg270548, but can't seem to reopen the issue, so I think the best thing is to report the bug separately.

So, in issue http://bugs.python.org/issue21136, performance enhancement https://hg.python.org/cpython/rev/91d7fadac271/ enabled a shortcut for some operations (__pow__ among them) to avoid reducing the result to lowest terms if it can be concluded it's already reduced.

However, the logic has a corner case that was handled incorrectly. If a negative Fraction is raised to a negative integer, the result is a Fraction with a negative denominator, which is not normalized and in fact breaks many other operations (which rightly assume their operands to be normalized).

>>> import fractions
>>> fractions.Fraction(-1, 2) ** -1
Fraction(2, -1)
>>> _ == -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 http://bugs.python.org/issue21136#msg215409. Alternative fix is to branch depending on the 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.

[BTW I'm not quite sure why the code in fractions.py is so general, with many weird cases trying to support every imaginable construction - maybe someone really wanted such a level of generality. I don't, so I'd be fine with this working only on ordinary int/int Fractions.]
msg270750 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-07-18 13:01
Oops, that's an embarrassing bug.

Branching depending on the sign sounds fine to me. There's no point worrying about supporting strange Fraction-like things without a concrete idea of exactly which such things we want to support.

Are you interested in writing a patch?
msg270808 - (view) Author: Vedran Čačić (veky) * Date: 2016-07-19 03:18
Unfortunately, until now I was just a happy user of Python. I suppose some day I would have to give something back, and now is as good a day as any:-), but I have studied https://docs.python.org/devguide/ for a while and it seems really scary.

It means I have to install and get acquainted with Mercurial [BTW I thought Python was on git since this year, it seems PEP 481 was just wishful thinking:(], and probably with Visual Studio since I use Windows - and I have never successfully installed that (I have some weird academic Windows licence it doesn't like, and it seems really hard to install for a single non-admin user, which is a must since this is actually not my machine:).

So, let's put the cards on the table: if the idea of your post was to initiate me in the process of becoming a good open-source citizen, then I'll bite the bullet and try to do everything in my power to actually get my equipment into a state where I can contribute to Python - but it will take time. On the other hand, if the idea was to just fix the bug in time for 3.6b1, it would be a great deal simpler if you wrote the patch. :-/
msg270812 - (view) Author: Vedran Čačić (veky) * Date: 2016-07-19 04:31
If it is of any help, here is the patch I wrote online:

http://www.mergely.com/TwCVpiFp/

(also in attachment). I also took the liberty of properly isolating the _normalize argument by requiring it to be keyword-only (starting its name with underscore doesn't mean much if people could just call e.g. `Fraction(2, 3, 4)` without error).
msg271023 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2016-07-22 19:55
Vedran: The migration to git and GitHub is in progress.  The devguide is being moved today.  CPython itself should be done by the end of the year, but after 3.6.0 is released in Sept.

I am on Windows and yes, setting up on Windows can be a nuisance.  Learning VS is not needed, as one can just run PCBuild/build.bat to compile.  But installing 9 GB of even the free version, to use the compiler, is.  TortoiseHG makes minimal use of hg pretty easy.  I had never used any source control system before.  But this will be unnecessary soon.

I let Mark decide if he can use the diff as is.  Are the line numbers those of fractions.py, or do they need to be translated?
msg271060 - (view) Author: Vedran Čačić (veky) * Date: 2016-07-23 05:28
The .diff format of patch for fractions.py is at 
http://bugs.python.org/file43786/TwCVpiFp.diff

The line numbers in it are the newest I could get (from 
https://hg.python.org/cpython/file/default/Lib/fractions.py).

I would also add the test I was talking about (Fraction(-1, 2) ** -1), if I knew where to do it.
msg271067 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2016-07-23 09:24
Tests for fractions are in Lib/test/test_fractions.py.  In necessary, post the new code in a message.
msg272471 - (view) Author: Vedran Čačić (veky) * Date: 2016-08-11 18:41
Here is the code for the patch:

84c84
<     def __new__(cls, numerator=0, denominator=None, _normalize=True):
---
>     def __new__(cls, numerator=0, denominator=None, *, _normalize=True):
459,466c459,466
<                 if power >= 0:
<                     return Fraction(a._numerator ** power,
<                                     a._denominator ** power,
<                                     _normalize=False)
<                 else:
<                     return Fraction(a._denominator ** -power,
<                                     a._numerator ** -power,
<                                     _normalize=False)
---
>                 num = a._numerator
>                 den = a._denominator
>                 if power < 0:
>                     num, den, power = den, num, -power
>                     if den < 0:
>                         num = -num
>                         den = -den
>                 return Fraction(num ** power, den ** power, _normalize=False)

I tried to add the test to test_fractions.py, but unfortunately unittest reports 3 unrelated failures due to mismatch in error messages (why does it check exact messages of exceptions anyway?). But it should just be adding

        self.assertTypedEquals(F(-1, 2), F(-2) ** -1)

after line 408.

_Please_, can this go in before 15th?
msg272528 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-12 11:57
> _Please_, can this go in before 15th?

Note that this is a bugfix, not a new feature, so it can still go in after the 15th.
msg273282 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-21 08:47
Here's a patch (against the 3.5 tip). I've dropped the keyword-only `_normalize` change; I have no objections to that change, but it's independent of the fix, and should probably be a 3.6-only change.
msg273284 - (view) Author: Vedran Čačić (veky) * Date: 2016-08-21 09:38
> it's independent of the fix, and should probably be a 3.6-only change.

Fair enough. Two questions:

How/when does this appear in 3.6 line? I guess there is a standard timeline of how bugfixes are "forwardported", but I don't know what it is.

How do I make the _normalize "kwonlyfication"? Do I report a new issue and refer to this one? I really think that accepting `Fraction(2, 3, 4)` is simply a bug (though I don't mind if it's fixed only in >=3.6).
msg273285 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-21 09:55
> Do I report a new issue and refer to this one?

Sure, that would work. A patch that included the change and a test that checks that `Fraction(3, 4, True)` raises TypeError would be good, too.
msg273286 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-21 09:57
> How/when does this appear in 3.6 line?

After allowing a couple of days for review, I'll commit the issue_27539_fix patch to the 3.5 branch, then immediately merge it to the 3.6 "default" branch. So that fix should appear in the upcoming 3.6 beta1.
msg273296 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-08-21 13:38
LGTM.
msg273345 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-08-22 09:56
New changeset 7eea5b87f5fa by Mark Dickinson in branch '3.5':
Issue #27539: Fix unnormalised Fraction.__pow__ result for negative exponent and base. Thanks Vedran Čačić.
https://hg.python.org/cpython/rev/7eea5b87f5fa

New changeset 902e82f71880 by Mark Dickinson in branch 'default':
Issue #27539: Merge from 3.5.
https://hg.python.org/cpython/rev/902e82f71880
msg273346 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-08-22 09:57
Thanks, all. Closing as fixed.
History
Date User Action Args
2016-08-22 09:57:55mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg273346

stage: commit review -> resolved
2016-08-22 09:56:21python-devsetnosy: + python-dev
messages: + msg273345
2016-08-21 13:38:39serhiy.storchakasetnosy: + serhiy.storchaka

messages: + msg273296
stage: commit review
2016-08-21 09:57:15mark.dickinsonsetmessages: + msg273286
2016-08-21 09:55:14mark.dickinsonsetmessages: + msg273285
2016-08-21 09:38:32vekysetmessages: + msg273284
2016-08-21 08:47:04mark.dickinsonsetfiles: + issue_27539_fix.patch

messages: + msg273282
2016-08-21 08:04:38mark.dickinsonsetassignee: mark.dickinson
2016-08-12 11:57:45mark.dickinsonsetmessages: + msg272528
2016-08-11 18:41:43vekysetmessages: + msg272471
2016-07-23 09:24:11terry.reedysetmessages: + msg271067
2016-07-23 05:28:44vekysetmessages: + msg271060
2016-07-22 19:55:02terry.reedysetnosy: + terry.reedy
messages: + msg271023
2016-07-19 04:31:03vekysetfiles: + TwCVpiFp.diff
keywords: + patch
messages: + msg270812
2016-07-19 03:18:46vekysetmessages: + msg270808
2016-07-18 13:01:35mark.dickinsonsetpriority: normal -> high

messages: + msg270750
2016-07-17 08:19:53SilentGhostsetnosy: + rhettinger, mark.dickinson
2016-07-17 07:32:11vekycreate