Doing fast leftshift

[Décio Luiz Gazzoni Filho]

On Nov 11, 2005, at 12:47 PM, stiank at ii.uib.no wrote:

>
> Hi. I'm working on a very time-critical application witch includes  
> calculations
> with big integers (128bits, unsigned). Using GMP boosted the speed  
> alot, so I
> were really happy when I discovered it!
>
> However; I have a problem. I'm not able to do shifting of numbers  
> in a efficient
> way. As I couldn't find any methods for doing leftshift directly  
> (including
> wrapping around the edge) I created my own function for doing this  
> – using
> GMP-functions.
>
> It goes like this :
>
> //shifting number given # positions and putting the result into  
> result.
> void leftShift(mpz_t result, mpz_t number, int positions){
>   //The shifting:
>   mpz_mul_2exp(result, number, positions);
>   //And the wrapping:
>   for(int i=0;i<positions;i++){
>     if(mpz_tstbit(result, 128+i){
>       mpz_clrbit(result, 128+i);
>       mpz_setbit(result, i);
>     }
>   }
> }
>
> Any ideas about what's not good here? Are there any functions witch  
> does this
> directly witch I've missed?

I'm sorry, I replied a little too quickly. Apparently you're trying  
to do a rotation (i.e. multiplication modulo 2^128 - 1). In that case  
you can perform a left shift by the desired value (call it r), a  
logical right shift (i.e. unsigned division) by (128 - r) which is  
saved in a temporary value, then the bitwise OR of both.

Décio

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20051111/b7fcbebc/PGP.bin