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

问题描述

这是具有以下公式的线性同余生成器的 C 语言实现：

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

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

下面代码中的模数是 2^64−1。我想将模数重写为 2^64，当我尝试由于数据类型而出现错误时。由于 2^64 是 65 位，并且该函数具有包含 64 位的“uint64_t”数据类型。我寻找解决问题的解决方案，例如使用 128 位数据类型，但我在 Mac 上使用 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;
 }

标签： calgorithmrandomcryptography

这些函数中使用的模数不是$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 必须是静态的。它必须在下次调用该函数时保持其值。

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

问题描述

解决方案

推荐阅读