[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.