PEP 327: Decimal Data Type

[Jeff Epler]

> On 5 Feb 2004 09:16:51 -0500, aahz at pythoncraft.com (Aahz) wrote:
> >The problem lies precisely in that representation.  For starters, a
> >binary integer is O(n^2) for conversion to decimal printing.  Then

On Fri, Feb 06, 2004 at 06:56:03PM +0000, Bengt Richter wrote:
> Please clarify. What is your "n" in that?

"n" is the number of digits in the number, in this case.

A standard way to convert to base 10 looks like this:
    def base10(i):
        digits = []
        while i:
            i, b = divmod(i, 10)
            digits.append(b)
        digits.reverse()
        return digits
Each divmod() takes from O(n) down to O(1) (O(log i) for each successive
value of i), and the loop runs n times (i is shortened by one digit each
time).  This is a typical n^2 algorithm, much like bubble sort where the
outer loop runs n times and an inner loop runs 1-to-n times.

Jeff