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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]