On 10/16/07, Mark Dickinson <[EMAIL PROTECTED]> 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 _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
