C语言快速生成随机布尔值（Bernoulli(0.5)变量）的优化咨询

Great question—when speed is the top priority for generating Bernoulli(0.5) values in C, every tiny optimization adds up. Let’s break down your two questions and explore even faster approaches:

1. Is checking m < M/2 faster than comparing floating-point x < 0.5? #

Absolutely! This is a smart optimization that cuts out unnecessary overhead. Here’s why:

• Most high-quality double-precision RNGs work by first generating a uniform integer m in [0, M] (where M is often 2^53, the largest integer exactly representable in a double) before converting it to a float via m/M.
• Comparing the integer m directly to M/2 (a compile-time constant if M is a power of two—like 2^52 for M=2^53) skips both the division operation and the floating-point comparison. Integer comparisons are far faster than floating-point operations, and you avoid any tiny precision edge cases that could creep into the float conversion.
• For example, instead of:

  double x = (double)m / M;
  return x < 0.5;
  

  You can write:

  // If M is a power of two, use bit-shifting for even faster constant calculation
  return m < (M >> 1);
  

  This is a straightforward speed win without sacrificing any statistical quality if your original RNG was good.

2. Are there even faster implementations (with relaxed statistical requirements)? #

Yes! Since you only need a long period and roughly 50% probability (not strict uniformity), you can leverage bit-level operations from your RNG, which are the fastest possible operations in C:

• Single-bit extraction: Grab any single bit from the integer output of your PRNG. For most modern high-quality RNGs (like xoshiro256++, PCG, or even Mersenne Twister), individual bits (especially higher bits, if you’re worried about minor bias in lower bits) have roughly 50% probability of being 0 or 1. The fastest version is to take the least significant bit:

  // Assuming rng() returns a 64-bit unsigned integer from your PRNG
  return (rng() & 1);
  

  If you’re using a simpler RNG with known bias in lower bits (like some linear congruential generators), just shift to a higher bit instead:

  return (rng() >> 63) & 1;
  

• Batch generation: For even better throughput, pre-generate a large chunk of random bits (like a 64-bit integer) and consume one bit at a time. This amortizes the cost of generating a random number across 64 boolean values:

  static uint64_t batch_rand;
  static int bits_left = 0;
  
  bool fast_bernoulli(void) {
      if (bits_left == 0) {
          batch_rand = rng();
          bits_left = 64;
      }
      bits_left--;
      return (batch_rand >> bits_left) & 1;
  }
  

  This approach makes each boolean value generation almost free, since you only call the RNG once every 64 calls.

Just remember: even with relaxed stats, stick to a long-period PRNG (avoid the standard rand() if you need a long cycle) to ensure you don’t hit repetition early.

内容的提问来源于stack exchange，提问作者Gabriele