[Python-Dev] SIGCHECK() in longobject.c (original) (raw)

Mark Dickinson dickinsm at gmail.com
Tue Oct 20 10:39:31 CEST 2009

On Mon, Oct 19, 2009 at 9:58 PM, Tim Peters <tim.peters at gmail.com> wrote:

Don't want to hijack this thread, but this is the kind of use case justifying keeping the 3-argument pow in the decimal module.  People "playing" with number theory questions can learn a bag of tricks to worm around that non-decimal arithmetic can make it inconvenient & slow to get answers about decimal digits, but most people -- and especially beginners -- find life easier when doing calculations in decimal to begin with.  Then they can use obvious methods, and not get sidetracked by wondering why they take forever to finish.

That's true. I wouldn't relish the task of trying to teach the decimal module at the same time as introducing students to Python and to elementary number theory, though. It's not the most friendly module to get started with.

Although, to be fair, I started

decimal.getcontext().prec = 20000000 p10 = pow(decimal.Decimal(2), 43112609) before I started typing this, and am still waiting for it to finish ;-)

Hmm, yes. The decimal module isn't (currently) well set up for this sort of calculation, mostly because almost every operation is implemented by converting to binary, invoking the appropriate int/long arithmetic operation, and converting back. Since the conversion is O(n^2), even addition and multiplication of Decimal instances end up being O(n^2) operations at the moment, instead of getting the linear and Karatsuba (resp.) running times that they deserve.

(The exception is rounding operations, which don't do any decimal <-> binary operations, but operate directly on the coefficient in its representation as a string of decimal digits.)

This high-precision inefficiency could easily be fixed by using a dedicated 'decimal natural number' extension type for the Decimal coefficient, stored internally in base a suitable power of 10. I think this may be worth considering seriously. I'm not proposing this as an alternative to the huge task of rewriting the entire decimal module in C, by the way; it would be more a stop-gap measure that would be easy to implement, would slightly increase efficiency for normal operations, and vastly increase efficiency for high-precision operations.

OTOH,

decimal.getcontext().prec = 200 pow(decimal.Decimal(2), 43112609)   # get the first 100 digits (& then some) and pow(decimal.Decimal(2), 43112609, 10**100) - 1  # get the last 100 digits both appear to work instantaneously.

Right. Low precision Decimal operations should be fine. I don't really see the advantage of the second operation over a simple

pow(2, 43112609, 10**100)

though.

By the way, despite the above use-case, and despite the fact that I use it frequently, I still don't believe 3-argument pow belongs in the core. But that's probably a discussion topic for Python 4000.

Mark

More information about the Python-Dev mailing list