Semantics of toString

[Bill Baxter]

On Tue, Nov 10, 2009 at 9:16 AM, bearophile <bearophileHUGS at lycos.com> wrote:
> Bill Baxter:
>> Maybe it's just my ignorance of BigNum issues, but those links look to
>> me to be about divsion and not generating string representations.  Are
>> those somehow synonymous in BigInt land?
>
> Look the numeral() function inside here from those blog posts:
> http://www.dd.chalmers.se/~frejohl/code/div.py
>
> To convert a positive integer to string you have to keep dividing a number by 10, and accumulate the modulus as the digit, converted to ['0', '9']. When the number is zero you are done:
>
> n = 541489
> result = ""
> while n:
>    n, digit = divmod(n, 10)
>    result = str(digit) + result # don't do this
> print repr(result) # prints '541489'
>
> But all those large divisions are slow if the number is huge. So that div.py python program shows a faster algorithm that does something smarter, to decrease the computational complexity of all that.

Well, anyway, slowness of BigInt is not what Don was referring to.  He
was talking about the general slowness of a toString interface that
forces allocating enough memory to hold the entire result, instead of
being able to dole out the result piecemeal.

--bb