Search code examples
cgmp

What's the most efficient possible way to get the binary suffix of a number with GMP?

Equivalently I'd like to load x % 2^n into another mpz_t. It's not clear to me whether mpz_mod (manual) will be faster than something like:

mpz_t setSuffix(int n,mpz_t x){
  mpz_t y; 
  mpz_init_set_ui(y,0);
  for(int i=0;i<n;i++){
    if(mpz_tstbit(x,i)){
      mpz_setbit(y,i);
    }
  }
  return y;
}

(bit manipulation functions)

Can I do better here with some built in function, or is this the speed limit? It might be faster to run the loop backwards so allocation would only be done once.

Solution
    1. Calculate n/64, n%64.
    2. Transfer (n/64) times 64-bit ints.
    3. Transfer (n%64) bits individually.

    Additional optimization (instead of 3. above):

    1. Calculate (n%64)/32, (n%64)/16, (n%64)/8.
    2. If any of those is bigger than 0 (i.e. is equal to 1), copy that amount of data in one pass.
    3. Transfer the remaining (n%64)%8 bits individually.

    It might still be faster that 4.-6. above if:

    1. you calculate only (n%64)/8, (n%64)%8
    2. transfer (n%64)/8 bytes
    3. transfer (n%64)%8 bits

    From here, do some benchmarking and improve as needed.

    Note: I assumed you have a 64-bit system. For older systems, adjust as needed. Also, some of the math above might need some adjustments (in steps 4.-6.).