线性同余生成器LCG在c中如何实现模数2^64

Question

这是一个用C实现的线性同余生成器，它具有以下公式：

X_{n+1}=a*X_{n} \bmod m

下面是两个版本的线性同余生成器函数，第一个函数生成一个64位整数，第二个函数生成一个双整数。

下面的代码中的模数是2ˆ64−1，当我尝试因为数据类型而得到一个错误时，我想重写模数为2^64。因为2^64是一个65位，并且函数有一个包含64位的"uint64_t“数据类型。我寻找解决这个问题的解决方案，比如使用128位数据类型，但我在Mac上使用Xcode，它不支持Xcode，还有一些人建议使用GPM，但我不喜欢它。我考虑过将模块存储在数组中，但我不知道以后如何才能将最终输出变成64位整数。

有什么简单的方法吗？因为我需要第一个函数的最终输出是64位整数，而第二个函数的输出是双倍，所以以后我可以在进一步的计算中使用它们。

编辑：在代码中，模数有值m= 18446744073709551615，即2ˆ64−1，我想将其更改为m= 18446744073709551616，即2^64。因为数据类型，当我这样做时，我会得到一个错误。我如何改变模数为m= 18446744073709551616 = 2^64？

uint64_t linear_congruential()
   {
    uint64_t s= 1442695040888963407;// seed
    unsigned long long int m=18446744073709551615; // The Modulus 2ˆ64−1    
    uint64_t a=6364136223846793005; // the multiplier a
    s=(s * a )&m;
    return s;
    }

具有双重功能的第二种功能：

double linear_congruential_d()
 {
  double q;
  uint64_t s= 1442695040888963407; //seed
  unsigned long long int m=18446744073709551615; // The Modulus 2ˆ64−1
  uint64_t a=6364136223846793005 ; // the multiplier a
  s=(s * a )&m;
  q=s/m; 
  return q;
 }

Answer 1

这些函数中使用的模数不是$2^{64}-1$，而是$2^{64}$。

如果$x$是2的幂，则始终可以将模$x$除以：

s = s*a & (x-1);

这就是这里所做的。

这个操作在这里是多余的，因为通过切断128位长的结果中较高的64位，乘法的结果被自动截断为64位。简化版本：

uint64_t linear_congruential()
{
    static uint64_t s= 1442695040888963407; // seed
    const uint64_t a = 6364136223846793005; // the multiplier a
    s *= a;
    return s;
}

第二个功能不起作用。由于s和m是整数，s/m将作为整数除法，也就是说，结果将被舍入到下一个整数。(几乎)总是0。相反，你应该写：

q = s / (double)m;

编辑:变量s必须是静态的。它必须为函数的下一次调用保留其值。

Answer 2

顺便提一下，当将64位无符号整数转换为双时，标准方法是：

unsigned long long my_big_number = .....;
double my_double_number = my_big_number / (double)MAX_UINT;

但这可能会更快：

double my_double_number = ( static_cast<double>(my_big_number>>2) / 2.0);

这利用了IEEE的双精度位格式，如果您的整数是全范围64位，那么该双将在范围[ 0.0 .. 2.0 )。最后除以2.0 --也就是说，[ 0.0 .. 1.0 )的目标范围将比被(double)MAX_INT除以更快。