[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Not a bug report but a suggestion
From: |
Kevin Ryde |
Subject: |
Re: Not a bug report but a suggestion |
Date: |
19 Jan 2002 06:43:49 +1000 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) Emacs/20.5 |
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.