mpf_get_str() is slow for big numbers?

Torbjorn Granlund tg at swox.com
Mon Dec 1 00:53:18 CET 2003


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

--
Torbjörn


More information about the gmp-discuss mailing list