mpf_get_str() is slow for big numbers?

[delta trinity]

:)

Well, I guess that mpz_out_str is general for all bases.  For sure, the 
problem with arbitary bases is that it require divisions and remainder 
operations over the whole number, and for each digits.  Ex, for positive 
numbers, repeat:
1 - digit = number mod base
2 - number = number / base
3 - if number > 0, go to step 1.

Even if steps 1 can be done in the same step, this can meen a lot divisions 
for really big numbers.

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

Eric

>From: rob at haptek.com (rob shaw)
>To: gmp-discuss at swox.com
>Subject: Re: mpf_get_str() is slow for big numbers?
>Date: Sun, 30 Nov 2003 10:09:52 -0700
>
> >rob shaw <rob at haptek.com> writes:
> >>
> >> The installation of GMP went smoothly on a mac G4 under OS X, but I've
> >> noticed that
> >> the output of very large numbers via mpf_out_str() is painfully
> >> slow.
> >
> >Alas, it still uses a quadratic algorithm.  The next release will have
> >that fixed.  One workaround is to scale and convert to an integer,
> >since integer output is subquadratic.
>
>...i wrote a routine mpf_out_str16() which is specialized to write
>out hex characters to disk directly from the mpf_t variable, without
>allocating memory for the string, etc.  to write out 25 million hex digits
>mpf_out_str() took over 15 hours, the direct version, 3 seconds.
>the code, such that it is, is available on request.
>
>rob
>
>
>_______________________________________________
>gmp-discuss mailing list
>gmp-discuss at swox.com
>https://gmplib.org/mailman/listinfo/gmp-discuss

_________________________________________________________________
online games and music with a high-speed Internet connection!  Prices start 
at less than $1 a day average.  https://broadband.msn.com (Prices may vary 
by service area.)