[Python-Dev] C Decimal - is there any interest?

[Daniel Stutzbach]

On 10/16/07, Mark Dickinson <dickinsm at gmail.com> wrote:
> I'm almost sure that adding 40000 digit numbers together is not what
> Decimal was intended to be used for, but it still seems unreasonable
> that it takes almost 5 seconds to do such an addition.  The reason for
> the quadratic behaviour is that almost all the arithmetic routines in
> decimal.py, at some point, convert the coefficient of their
> argument(s) from a tuple of digits to a Python integer, and then do
> the reverse conversion to get a Decimal result;  both of these
> conversions (tuple of digits <-> integer) take time quadratic in the
> size of the tuple/integer.

Instead of (or in addition to) porting to C, wouldn't it be better to
improve the conversion algorithm?

Radix conversion can be done in O(n log**2 n) time using a divide and
conquer algorithm.

Such an algorithm can be found at the link below (search for "Radix
conversion"):
http://people.cis.ksu.edu/~rhowell/calculator/comparison.html

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC