Recent changes to mpn_get_str/mpn_set_str

Marco Bodrato bodrato at
Thu Mar 2 07:29:34 UTC 2017


Il Mar, 28 Febbraio 2017 11:04 pm, Torbjörn Granlund ha scritto:
>   Now the crossover is around 5 limbs.
> The cross-over between old base-case code for base 10 and the
> new "base-case" code?

Yes, for 6 limbs or more, the new code is faster than the old one for all
the bases I tested. For smaller operands, I have to analyse more
carefully, and behavior changes when the base changes.

>   Are divrem_[12] the best function we currently have to obtain
>   the quotient only when we divide by 1 or 2 limbs?

> For cutoff point of 5, will divrem_1/divrem_2 ever get used? I'd
> expect the choice to be between mpn_sbpi1_div_q and mpn_dcpi1_div_q.

I'm not currently implementing the new code as something in between _bc_
and _dc_, with its own threshold, but as a complete replacement for the
current _bc_. That's why I need also small cases.

Moreover, I divide by a power of the odd part of the base. If base=192, I
use powers of 3. log(192)/log(3)>4.5 , so that up to 9 limbs to convert,
the power used as a divisor surely fits in 2 limbs.

Anyway I still hope I'll be able to refine the code so that it can replace
the current, for all sizes.

Maybe I should change my strategy a little. I currently estimate the
number of digits exp with
 MPN_NORMALIZE (up, un);MPN_SIZEINBASE (exp, up, un, base);
Then I divide by base^(exp-1). This minimizes the power to be computed,
and may give the first digit "for free" (if exp, estimated by SIZEINBASE,
is exact) or at least allows to early know the exact number of digits (I
directly write to the final string).
All this initial estimates probably adds too much overhead for the input
of just a few limbs. I should try with a straighter coding...



More information about the gmp-devel mailing list