mpf_get_str() is slow for big numbers?
delta trinity
deltatrinity at hotmail.com
Sun Nov 30 16:44:20 CET 2003
:)
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.)
More information about the gmp-discuss
mailing list