Implement a logical shift for mpz_t
Marc Glisse
marc.glisse at inria.fr
Sat May 8 08:31:59 UTC 2021
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
More information about the gmp-discuss
mailing list