Recent changes to mpn_get_str/mpn_set_str

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> I think sliding-window only applies to finate rings...

For complexity analysis, there's a big difference between rings with a
representation where ring operations are more or less the same cost for
all elements. Which I'd assume is the case considered by most of the
literature. And rings where costs are widely varying depending on some
type of "element size".

> And what you are talking about is essentially k-ary exponentiation in Z,
> not sliding window.  Isn't it?

I was thinking that either could apply, but mainly in the case that

1. The base is small, so that we get a reasonable table of single-limb
   powers. E.g, for the base 10 we could fit powers up to 10^15 in a
   64-bit limb. Which would be a 4-bit lookup for k-ary or a 3-bit
   lookup for sliding window, unless I misremeber how it works.

2. The result is of moderate size, so that the non-squaring work is a
   measurable proportion of the total work.

But on the other hand, it might be better to note that, e.g., 10^19 fits
in 64 bits, and compute 10^e as (10^19)^(floor(e/19)) * 10^(e mod 19).
Or even better, handle the power of 2 separately and note that 5^27 fits
in a 64-bit limb.

Which perhaps is precisely what the mpz code already is doing?

BTW, I think (10^19)^floor(e/19) might be an example where one could
beat simple squaring slightly, even if e is a power of 2.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.