Title: Three argument power issues
Type: behavior Stage: needs patch
Components: Library (Lib) Versions: Python 3.2
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: mark.dickinson, rhettinger, skrah
Priority: low Keywords: patch

Created on 2009-10-03 13:59 by skrah, last changed 2011-11-19 16:33 by mark.dickinson. This issue is now closed.

File name Uploaded Description Edit
issue7049.patch mark.dickinson, 2009-10-03 18:45 review
Messages (19)
msg93493 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2009-10-03 13:59
If precision 1 is aupported, the following results should not be NaN:

Python 2.7a0 (trunk:74738, Sep 10 2009, 11:50:08) 
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from decimal import *
>>> setcontext(Context(prec=1, rounding=ROUND_UP,
Emin=-999999999999999999, Emax=999999999999999999, capitals=1, flags=[],
>>> pow(Decimal(0), Decimal(3), Decimal(70))
>>> pow(Decimal(3), Decimal(0), Decimal(70))
msg93499 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-10-03 15:51
This behaviour was deliberate:  since the standard doesn't cover three-
argument pow, I more-or-less made up my own rules here.  :)

In this case, I (somewhat arbitrarily) decided that to ensure that any 
possible pow(a, b, m) result could be represented, m should be strictly 
less than 10**current_precision.  In general, you'd expect to make lots
of pow(a, b, m) calls with the same m and differing a and b;  it seems 
less error-prone to have them all these calls fail/pass together than 
have those with small results pass, and those with larger results fail.

Not that I expect there's a single person on this planet who's using 
three-argument pow with the Decimal type.  :)

Looking back at this, I'm not quite sure why I chose 'strictly less 
than' rather than 'less than or equal to'.
msg93502 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-10-03 18:13
Unless anyone else disagrees, I'm going to call this a 'won't fix':  I'm 
happy with the current behaviour.  I would like to relax the condition on 
the modulus from 'modulus < 10**prec' to 'modulus <= 10**prec', though, so 
I'm leaving the issue open for that.
msg93503 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-10-03 18:45
Here's a patch.
msg93511 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2009-10-03 22:36
I don't think early abortion based on m and the current precision is a
good idea. Then we have the situation that this works (prec=4):

(Decimal(7) ** 2) % 100000

But this does not:

pow(Decimal(7), 2, 100000)
msg93528 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-10-04 09:41
Shrug.  That doesn't really bother me.  x**y%z and pow(x, y, z) aren't 
going to match anyway, as soon as x**y has to be rounded.

What would bother me more is the idea of having, with precision 4:

pow(3, 22, 12347) -> nan
pow(3, 23, 12347) -> 7820
pow(3, 24, 12347) -> nan
pow(3, 25, 12347) -> 8645
pow(3, 26, 12347) -> 1241

(or a similar phenomenon with the 1st argument varying and 2nd and 3rd 
arguments fixed).  Or something that called pow(x, 3, 100003) with 
precision 5, and worked for all but 3 possible values of x.  That sort 
of thing is the cause of hidden bugs.

It's all academic really;  no-one's going to use Decimal's 3-argument 
pow.  I'm not really sure why it's supported at all.  Come to that, I 
don't really understand why Python's 3-argument pow belongs in the core 
interpreter (as opposed to somewhere in the standard library).  If it 
hadn't been there, and if __pow__ didn't accept a third argument, I 
suspect no-one would have tried to implement 3-argument pow for Decimal.
msg93710 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2009-10-07 18:52
This whole thing is indeed a matter of taste, so I'd close the bug if no
one else is interested.
msg93711 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-10-07 18:56
I would like to look at this for a bit before it gets closed.
msg93712 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-10-07 18:59
Raymond, can I recommend deprecating and eventually removing three-
argument pow support from Decimal?
msg93717 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2009-10-07 20:10
Deprecate on the grounds that it is slow in or the
InvalidOperation issue?

I think pure integer arithmetic with the decimal type always requires
attention from the user, since in many functions one has to check for
Rounded/Inexact in order to get meaningful results. Here one has to
check for InvalidOperation, so I don't think it's a big deal. (This is
also the reason that I don't find the inconsistencies that you listed
particularly bothersome.)

If slowness is the reason: If any C module makes it into Python, this
would not be an issue any longer.
msg93720 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-10-07 20:17
I was suggesting that it be deprecated on the grounds that:

(1) It's not part of the Decimal standard.
(2) It's not implemented for Python (binary) floats, so why implement
    it for decimal floats?
(3) It's severely use-case challenged.

It's a pure integer-based number-theoretic function that has no place in 
the Decimal module.
msg93722 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2009-10-07 21:07
(1) is clearly true. I wonder about (2) and (3):

The decimal data type is specified to be usable for integer arithmetic.
With a high precision (and traps for Rounded/Inexact) I think it's
reasonably convenient to use.
msg99735 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2010-02-22 14:01
This is a very loosely related issue, but I think it fits in here.
To be consistent with the documentation, the three argument power
should use the ideal exponent:

>>> c = getcontext()
>>> c.prec = 400
>>> Decimal('1E400') % Decimal('1123123E5')
>>> pow(Decimal('1E400'), 1, (Decimal('1123123E5')))
msg99746 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-02-22 15:21
The ideal exponent for three-argument pow should definitely be zero.  You're returning what's essentially an integer, loosely disguised as a decimal instance.
msg99752 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-02-22 15:43
I've fixed the docs to accurately describe three-argument pow results (the exponent in particular) in r78312 through r78315.
msg99820 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2010-02-22 20:05
I've tried to pinpoint exactly what I don't like about the current
behavior, and the main reason is that it violates my mental model
of how the functions in the specification generally behave:

1) Functions take arbitrary precision input.

2) Functions try to preserve as much of the exponent
   information of the input as possible.

With these in mind, it's easy to specify powmod() as:

(a ** b) % c, calculated with unlimited precision. Raises if
the final result does not fit in the current precision.

It is not totally clear to me why the result should have exponent 0
because it is an integer. Decimal("1E3").to_integral() also preserves
the exponent information.
msg99825 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-02-22 20:30
Well, the real problem is that powmod doesn't really belong in the decimal module at all.  It's not a natural primitive arithmetic operation; it's certainly not naturally a floating-point operation; nothing like this appears in any floating-point standard that I'm aware of; and its (few) use cases are very different from typical decimal use cases.  I'd like to bet that it currently has precisely 0 users.  Trying to shoehorn powmod into the decimal module and make its semantics fit with the rest of the module seems a little pointless to me.

Really, what's the point of making any sort of attempt to preserve exponents in 3-argument pow?  Having the result exponent be 0 is clean, simple to understand, simple to implement (which your proposal is not), and matches the use-cases.  The restriction on the modulus also matches the use-cases:  typically, the modulus m is fixed, and you won't have any expectations about the output of powmod(a, b, m) except that you'll know the result is an integer in the range 0 <= x < m.  Having powmod reject m's for which only part of this range is representable avoids hard-to-find bugs where powmod(a, b, m) works for most values of a but then unexpectedly fails for some particular value of a because the result is just larger than can be represented.
msg122025 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-11-21 23:55
+1 for deprecating three-arg pow for the reasons given.
A user is much better-off composing well-defined operations
than using our short-cut, with our chosen assumptions.
Apologies for taking so long to think this one through.
msg147951 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-11-19 16:33
Closing as won't fix.  Even deprecation doesn't seem worth the effort here.
Date User Action Args
2011-11-19 16:33:34mark.dickinsonsetstatus: open -> closed
resolution: wont fix
messages: + msg147951
2010-11-21 23:55:32rhettingersetassignee: rhettinger -> mark.dickinson
messages: + msg122025
versions: - Python 2.7
2010-02-22 20:30:09mark.dickinsonsetmessages: + msg99825
2010-02-22 20:05:44skrahsetmessages: + msg99820
2010-02-22 15:43:42mark.dickinsonsetmessages: + msg99752
2010-02-22 15:21:09mark.dickinsonsetmessages: + msg99746
2010-02-22 14:01:08skrahsetmessages: + msg99735
title: NaN result in pow(x, y, z) with prec 1 -> Three argument power issues
2009-10-07 21:07:47skrahsetmessages: + msg93722
2009-10-07 20:17:42mark.dickinsonsetmessages: + msg93720
2009-10-07 20:11:00skrahsetmessages: + msg93717
2009-10-07 18:59:17mark.dickinsonsetmessages: + msg93712
2009-10-07 18:56:50rhettingersetassignee: mark.dickinson -> rhettinger

messages: + msg93711
nosy: + rhettinger
2009-10-07 18:52:02skrahsetmessages: + msg93710
2009-10-04 09:41:16mark.dickinsonsetmessages: + msg93528
2009-10-03 22:36:56skrahsetmessages: + msg93511
2009-10-03 18:45:58mark.dickinsonsetfiles: + issue7049.patch
keywords: + patch
messages: + msg93503
2009-10-03 18:13:22mark.dickinsonsetpriority: low

assignee: mark.dickinson
components: + Library (Lib)
versions: + Python 2.7, Python 3.2
type: behavior
messages: + msg93502
stage: needs patch
2009-10-03 15:51:58mark.dickinsonsetmessages: + msg93499
2009-10-03 14:00:25skrahsetnosy: + mark.dickinson
2009-10-03 13:59:23skrahcreate