将随机整数转换为范围 [min,max] 而不分支

Question

我得到了 hold on an SUPER-FAST algorithm，它均匀地生成一个随机字节数组。比std库的c++均匀分布和mersenne-twister快6倍

数组的个数可以被4整除，所以可以理解为整数数组。将每个条目转换为一个整数，生成 [INT_MIN, INT_MAX] 范围内的值。但是我怎样才能将这些整数值转换为介于我自己的 [min, maximum]?

之间呢？

我想避免任何 if-else，以避免分支。

也许我应该应用一些按位逻辑，以丢弃每个数字中不相关的位？（因为所有剩余的未屏蔽位无论如何都将是 0 或 1）。如果我可以在我的最大值中提取最高有效位，我可以在我的整数中屏蔽比那个更重要的任何位。

比如我要我的max是17，那么二进制形式就是00010001。也许我的面具会看起来像 00011111？然后我可以将它应用于数组中的所有数字。

但是，这个掩码是错误的......它实际上允许值高达 (1+2+4+8+16) :(

我能做什么？另外，如何照顾 min?

编辑

我在我的应用程序的每一帧为神经网络生成数百万个数字。我设法使用 AXV2 将代码矢量化为浮点变体（使用），但也需要让整数工作。

Answer 1

核心思想是使用模而不是按位掩码，这在非 2 的幂的情况下是无用的。没有分支也是一个有点奇怪的要求。你想要的是“足够快”，而不是“没有分支和按位掩码”。

所以假设我们有一个函数

int rand();

均匀生成一个随机整数。如果 max 的形式是 2^n-1 那么下面的

rand() % (max+1)

将统一生成 [0,max] 范围内的随机整数。那是因为整数的总数是2的幂。

现在如果 min 和 max 使得 max-min 的形式是 2^n-1 那么下面的

(rand() % (max-min+1)) + min

将统一产生一个范围在[min, max].

内的随机整数

但是当 max-min 不是 2^n-1 形式时会发生什么？那我们就不走运了。 (rand() % (max-min+1)) + min 方法仍将生成一个 [min, max] 范围内的随机整数，但不再统一。这是为什么？因为当 n 是固定的而不是 2 的幂时，那么给出具体 r = x % n 结果的整数总数取决于 r.

不过方法还不错。 max-min 值越大越接近均匀分布，通常在实践中已经足够好了。而且速度非常快，没有分支。

另一个例子是

upper = get_upper_power_of_2(max - min)

do
{
    tmp = rand() % upper;
} while (tmp > max - min);

result = tmp + min;

这种方法很好属性，它是统一的，但它没有停止属性，即理论上这个算法可能永远不会停止。它也有分支。但在实践中它确实停止得非常快（很有可能），所以它是一种非常常见的算法。例如，它在标准 Java 库中。

当 max-min 溢出时（即当 min 是一个大的负数时），这两种方法当然都有问题，如果我们切换到无符号整数然后再切换回整数，则可以解决这个问题。

据我所知，当 max 不是来自 01 统一生成器的 2^n-1 形式时，没有算法可以在 [0, max] 中生成随机整数结果是统一的，它已经停止属性。我认为不可能存在这样的算法，但我没能在计算机科学中找到合适的结果。

Answer 2

But how can I transform these integer values to lie between my own [min, maximum]?

由于范围可能不是 2 的幂，因此位掩码已失效，但您已经发现了。

Modulo 也出来了，它在 AVX2 中不作为本机操作存在（即使存在，也不一定会使其有效）。

还有另一种选择：乘高，使用 _mm256_mul_epu32（不幸的是，对于 32 位数字，没有“纯”乘高，就像 16 位数字一样，所以我们只能使用只做 50% 有用工作的操作）。那里的想法是采用输入数字 x（全范围）和所需范围 r，然后计算 r * x / 2^32 其中除法是隐式的（通过取乘积的高半部分来实现） ).

x / 2^32 本来是 [0.0 .. 1.0) 中的一个数字（不包括 1.0），如果它被解释为有理数，则乘以 r 然后将范围扩展为 [0.0 .. r)（不包括 r）。这不是它的计算方式，而是公式的来源。

通过向缩放结果添加 min 可以轻松设置范围的最小值。

在代码中（略微测试）：

__m256i squish(__m256i x, int min, int max) {
    __m256i sizeOfRange = _mm256_set1_epi32((unsigned)max - min);
    __m256i scaled_even = _mm256_shuffle_epi32(_mm256_mul_epu32(x, sizeOfRange), 0xB1);
    __m256i scaled_odd = _mm256_mul_epu32(_mm256_shuffle_epi32(x, 0xB1), sizeOfRange);
    __m256i scaled = _mm256_blend_epi32(scaled_even, scaled_odd, 0xAA);
    return _mm256_add_epi32(scaled, _mm256_set1_epi32(min));
}

它仍然是一个独占范围，它无法处理完整的 [INT_MIN .. INT_MAX] 作为输出范围。甚至无法指定它，它最多可以做的是 [INT_MIN .. INT_MAX) （或者例如零偏移量的等效范围： [0 .. -1) ）。

它也不真的均匀，出于同样的原因，简单的基于模数的范围缩减并不是真正均匀的，你就是不能公平地划分N弹珠超过 K 个垃圾箱，除非 K 恰好将 N 平均分配。

Answer 3

如果一个值中有 2^N 个随机位，您可以通过以下操作将其放入整数范围：

r = ((value * (max-min)) >> N) + min

实际上，您将您的值视为乘法分数。你保证得到 `[min...max)'

中的值

这最终成为两个可向量化的操作：mulhi、'add'

r = _mm256_add_epi16(
      _mm256_mulhi_epi16(value, _mm256_set1_epi16(max-min)), 
    _mm256_set1_epi16(min));

虽然如果你想要 32 位，看起来你需要两个 mul_epi32 和一个随机播放才能得到你的结果。

对于 64 位值，请参阅：（尽管它不支持向量化形式）

将随机整数转换为范围 [min,max] 而不分支

Transform random integers into range [min,max] without branching

c++

bit-manipulation

simd

avx2