mpf_get_str() is slow for big numbers?
tg at swox.com
Mon Dec 1 22:39:37 CET 2003
Torbjorn Granlund <tg at swox.com> writes:
In some bases though, like base 2, 4, 16, the process can be accelerated by
dropping the divisions. Only masks are needed. No need to even use
extensive shifts operations. Just run through each limbs and do a AND mask.
I wonder if GMP is built with such optimizations. The speed difference may
come from that. With the optimization, for base 16 for example, the runtime
become linear to the number of digits (O = ln(n))
No need to wonder. A great feature of GMP is that it comes with
source code. It is Free Software, remember. :-)
In GMP 4.1.2, mpz radix conversion is O(n) for bases 2^t, and
O(n^2) for other bases. mpf radix conversion is O(n^2) for all
(In the next major GMP release, both mpz and mpf will be O(n) for
bases 2^t and O(n*log(n)) for other bases. They will be based on
common mpn_get_str and mpn_set_str with that property.)
Correction: The O(n*log(n)) code is already available in GMP 4.1.2
through mpz output conversions.
The difference between 4.1.2 and the current development code, is
that in the latter, mpf output conversions use mpn_get_str, and
thus runs just as fast as mpz output conversions.
More information about the gmp-discuss