[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gmp-discuss
Subject:    Re: Implement a logical shift for mpz_t
From:       Jan_Claußen <jan.claussen10 () web ! de>
Date:       2021-05-08 10:51:47
Message-ID: 0D0D7264-916C-4958-A82B-289EE5A087D2 () web ! de
[Download RAW message or body]

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@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
_______________________________________________
gmp-discuss mailing list
gmp-discuss@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-discuss


[prev in list] [next in list] [prev in thread] [next in thread]