Re: Not a bug report but a suggestion

[Kevin Ryde]

Max Neunhoeffer <address@hidden> writes:
> 
> I happened to calculate 12345678901^11111 (it has about 112000 decimal
> digits). This took only 0.1 seconds or so but to write the result out
> took about 3 seconds.

If you have a peek at mpn_get_str you'll see it's basically O(n^2),
and becomes pretty slow for large inputs.

> I wrote a little C routine using GMP to accomplish this task in about
> 0.14 seconds on the same machine.

That's a bit of a speedup. :)

> The trick is simple: Just divide the number by a big power of 10 to
> approximately cut it in two equal pieces and repeat this process.

Some sort of divide and conquer base conversion has been on the todo
list for a while.

Arguably big numbers are better input and output in hex or octal,
though it'd be nice for non power-of-2 bases to have a good algorithm.

>   mpz_fdiv_qr(q,r,x,pow10tab[j]);

Torbjorn has a theory that it can be done without division, but I'm
not sure what that involves.