dickinsm at gmail
Oct 20, 2009, 1:39 AM
Post #10 of 16
(903 views)
Permalink
|
On Mon, Oct 19, 2009 at 9:58 PM, Tim Peters <tim.peters [at] gmail> 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
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com
|
