Re: Lengthy numbers

Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:

To solve that problem conversions from string->int and
int->string were disallowed.

The obvious conversion algorithms use quadratic time but it seems to me
that O(n log n) is doable with some careful programming.  For example,
people have computed pi to billions or trillions of decimal places.

I believe GMP uses the Toom-Cook algorithm for multiplication once the
numbers are big enough.  I don't know whether that is also used for
decimal conversions.

Page 14 of http://maths-people.anu.edu.au/~brent/pd/rpb032.pdf discusses
base conversion.  That link is from a stackexchange thread that I found
with web search.