mpf_get_str() is slow for big numbers?

[Torbjorn Granlund]

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
  bases.
  
  (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.

--
Torbjörn