如何正确进行 GMP 位移？

Question

我需要使用高精度整数进行一些计算，并希望使用 GMP 库。我希望这里有人有经验，因为我不明白如何使用位移位。我正在尝试使用下面的代码。代码可以编译，但 b 仍然包含 0。

https://gmplib.org/manual/Low_002dlevel-Functions

#include <stdio.h>                                                                                                                                                                                                                           
#include <gmp.h>                                                                                                                                                                                                                             
                                                                                                                                                                                                                                             
int main()                                                                                                                                                                                                                                   
{                                                                                                                                                                                                                                            
                                                                                                                                                                                                                                             
    mpz_t a;                                                                                                                                                                                                                                 
    mpz_t b;                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                             
    mpz_init2(b, a->_mp_size);                                                                                                                                                                                                               
    mpz_set_str(a, "1", 16);                                                                                                                                                                                                                 
                                                                                                                                                                                                                                             
    mp_limb_t bits = mpn_lshift(b->_mp_d, &a->_mp_d[0], a->_mp_size, 1);                                                                                                                                                                     
                                                                                                                                                                                                                                             
    gmp_printf("%Zx\n", a);                                                                                                                                                                                                                  
    gmp_printf("Bits shifted %M\n", bits);                                                                                                                                                                                                   
    gmp_printf("%Zd", b);                                                                                                                                                                                                                    
                                                                                                                                                                                                                                             
    return 0;                                                                                                                                                                                                                                
}      

Answer 1

下面的代码与 一起用于mpz_fdiv_q_2exp右移和mpz_mul_2exp左移mpz_tdiv_r_2exp。mpz_tdiv_r_2exp是必要的，因为数据倍增时大小会增加。

#include <stdio.h>                                                                                                                                                                                                                           
#include <gmp.h>                                                                                                                                                                                                                             
                                 

int main()                                                                                                                                                                                                                                   
{                                                                                                                                                                                                                                            
                                                                                                                                                                                                                                             
    mpz_t a;                                                                                                                                                                                                                                 
    mpz_t b;                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                             
    mpz_init_set_str(a, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16);                                                                                                                                                                                  
              
    for ( int i = 0; i < 128;  i++) {
        
        //left shift
        mpz_mul_2exp(b,a,I);
        //This is faster than `mpz_mod` since we are in 2^128 
        mpz_tdiv_r_2exp(b,b,128);
        
        //right shift
        //mpz_fdiv_q_2exp( b,a,i);     
    
        gmp_printf("\n%#40Zx", b); 
    }
    
    gmp_printf("\n%Zd", a);
    
    return 0;                                                                                                                                                                                                                                
} 

部分输出

      0xffffffffffffffffffffffffffffffff
      0xfffffffffffffffffffffffffffffffe
      0xfffffffffffffffffffffffffffffffc
      ...
      0xe0000000000000000000000000000000
      0xc0000000000000000000000000000000
      0x80000000000000000000000000000000

GMP 手册第 35 页

对于正 n mpz_fdiv_q_2exp 和 mpz_tdiv_q_2exp 都是简单的按位右移。

注意：可以直接使用mpn_lshiftand mpn_rshift，但是，这需要在开发库下进行更多的编码和测试。从mpz_mul_2exp的源代码中可以看出它是如何更复杂的。