Implement a logical shift for mpz_t

[Jan Claußen]

I know that GMP is mainly designed for doing arithmetic operations and that carrying bits over multiple limbs is not going to be efficient. For me it just serves as means to quickly try out a theory that I would later implement in a more efficient way.

I was just looking for universal shift functions and the ones proposed do the trick. The reason for my email was the proposition of an official implementation that you can find either searching for shift in the PDF documentation and adding it to the suggested category. You could also add a note that GMP wasn’t designed for this. So everyone would know what to expect.

I think it is a very interesting library, but think that the documentation is too lean. It would be nice to have examples for every function as the e.g. the Microsoft C++ port of GMP has in its documentation. (Couldn’t find the link just now.)

Maybe also link this tutorial. Just stumbled over it 
https://home.cs.colorado.edu/~srirams/courses/csci2824-spr14/gmpTutorial.html

I was searching for a way to bit shift for hours. Just saying.

> Am 08.05.2021 um 10:32 schrieb Marc Glisse <marc.glisse at inria.fr>:
> 
> On Thu, 6 May 2021, Jan Claußen wrote:
> 
>>> So the functions exist, you are just confused why they are not called shift?
>> Yes, I was searching for shift functions in the documentation and only found the low-level ones, which I did not understand. So yes, I think they should be renamed or listed in the integer bit-fiddling section.
>>> Do you assume that your numbers are non-negative?
>> Yes, I know they are.
>>> Are you (badly) trying to emulate fixed size numbers?
>> Yes, the fixed size of the registers is important for my application, so I am emulating the usual shift behavior.
> 
> mpz_t is meant to represent unbounded integers. Using it for a fixed size is bound to be less convenient, like it would be to use long to represent an integer type of fixed size 13 bits.
> 
> The lshift function you are missing might be something like mpz_mul_2exp_mod_2exp in the current terminology, you would need to pass the size as argument, as there is no way to guess from a number how many implicit leading zeros are part of the fixed size. Doing it as 2 operations is not that bad, even if it is slower than a dedicated function could be.
> 
> It could make sense to add to the section "Logical and Bit Manipulation Functions" of the documentation a sentence saying that shifts are handled as multiplications and divisions, possibly with a link to the sections on arithmetic and division.
> 
> Depending on the exact properties you need for your fixed size integer, it could make sense to define your own type with fixed size storage, that would call the low level mpn_* functions.
> 
>>>> On Thu, 6 May 2021, Jan Claußen wrote:
>>> 
>>> > I am just fiddling around with mpz_t variables and it took me quite a long time to come up with a bit shifting method with some help of the Stackexchange hive mind.
>>> Might as well give the link https://stackoverflow.com/q/67388748/1918193
>>> Do you assume that your numbers are non-negative?
>>> > These are the functions I have now:
>>> > inline void mpz_lshift(mpz_t rop, mpz_t op1, mp_bitcnt_t op2) {
>>> > mpz_mul_2exp(rop,op1,op2);
>>> > mpz_tdiv_r_2exp(rop, rop, mpz_popcount(op1));
>>> > }
>>> 
>>> No idea what that weird operation is supposed to be. mpz_mul_2exp shifts
>>> left, and that's that. Are you (badly) trying to emulate fixed size
>>> numbers?
>>> 
>>> > inline void mpz_rshift(mpz_t rop, mpz_t op1, mp_bitcnt_t op2) {
>>> > mpz_fdiv_q_2exp(rop, op1, op2);
>>> > }
>>> >
>>> > Is this a practical solution? There is probably a better way to do this in assembly, but it works for now. I just wonder why no functions like this exist yet. Is there a good reason?
>>> 
>>> So the functions exist, you are just confused why they are not called
>>> shift?
>>> 
>>> --
>>> Marc Glisse
> 
> -- 
> Marc Glisse