我正在C的一个项目中工作，我想在以下条件下逐步改变uint32_t:
- 位翻转的概率从最低有效位(LSB)的概率为1/2开始，然后左边的下一个位为1/4，下一个为1/8，以此类推(参见示例数组)。
- 在位
k被翻转后，概率(k)的值根据第一步中设置的分布重新分配到所有其他位。 - 概率(k)设为零。
我认为这些概率最好存储在长度为32的双精度数组中，因此一个非常有用的答案将是一个函数，它接受长度为32的双精度数组和一些要排除的整数，并返回一个修改后的长度为32的数组。
是否可以通过使用步骤1的过程生成一个长度为31的不包括k的数组，将每个值乘以array[k]的值，然后创建一个长度为32的包含array[k] = 0的数组并将其添加到输入数组(在设置input[k] = 0之后)来实现?
一个问题，我想象可能会发生，但我不确定如何解决:
- 在第一步中，这些概率都是1.)足够大，可以用双精度和2.)2的幂表示，所以它们是精确表示的。然而，没有很好的理由让它们保持这种状态。下面的示例数组和为1，因为它们都是可精确表示的。同样，我没有理由假设这对其他值也是成立的。我不清楚如何保持粗略的实用能力，以一种相当于从一个和为1的分布中提取的方式进行选择。
答案解决方案必须在C中，因为项目中的其余代码是。抱歉，我相信在其他语言中有很酷的方法来解决这个问题。也许R中的二项包会有这样的东西，但这没有帮助。一个类似C的语言，我可以手动调整代码在C中工作也很好。
我在台式计算机上控制开发环境，所以任何能使这变得容易的库都是受欢迎的。谢谢。此外，我不期望有任何性能限制，所以代码缓慢或需要存储表，这是很好的。
我这里的例子使用双精度，但这不是确定的。我来问这个问题是因为我不知道该怎么做。如果你有一个完全适用于整数的答案，那么我很乐意看到。
<<h3>例子数组/h3>void create_array32(double array[32]) {
int i;
for (i = 0; i < 32; i++) {
array[i] = pow(2, -(32 - i));
}
}
// The output, if that is easier to work with
double example[32] = {
0.0000000002328306, 0.0000000004656613,
0.0000000009313226, 0.0000000018626451,
0.0000000037252903, 0.0000000074505806,
0.0000000149011612, 0.0000000298023224,
0.0000000596046448, 0.0000001192092896,
0.0000002384185791, 0.0000004768371582,
0.0000009536743164, 0.0000019073486328,
0.0000038146972656, 0.0000076293945312,
0.0000152587890625, 0.0000305175781250,
0.0000610351562500, 0.0001220703125000,
0.0002441406250000, 0.0004882812500000,
0.0009765625000000, 0.0019531250000000,
0.0039062500000000, 0.0078125000000000,
0.0156250000000000, 0.0312500000000000,
0.0625000000000000, 0.1250000000000000,
0.2500000000000000, 0.5000000000000000}
不维护概率数组，而是维护相应的选择频率数组:
uint32_t frequencies[32];
for (int i = 0; i < 32; i++) {
frequencies[i] = (uint32_t) 1 << (31 - i);
}
如果你愿意，你可以预先计算这些起始频率，并把它们放在初始化器中，而不是在运行时计算它们。
每次你想做一个选择，
计算频率累计和的数组:
uint32_t cumulative[33] = {0}; for (int i = 0; i < 32; i++) { cumulative[i + 1] = cumulative[i] + frequencies[i]; }在0(含)到
cumulative[32](不含)之间生成一个(均匀分布的)随机数x查找值
n，使cumulative[n] <= x && x < cumulative[n + 1]。这个n是选择的比特数。你可以使用二分搜索，但线性搜索会更简单，而且只搜索32个项目，速度也差不多。
为了不进一步考虑n位，只需将其频率设置为0:
frequencies[n] = 0;
当您计算下一个选择的新累积总和时，自然会将n排除在考虑之外，并且通过计算修订的总数，调整所有剩余选项的概率。
int choose_bit(double array[32]) {
double cumsum[32] = { 0 };
compute_cumulative_sum(array, cumsum);
// https://stackoverflow.com/a/6219525
double r = (double)rand() / (double)RAND_MAX;
int i = 0;
for (i = 0; i < 32; i++) {
if (r <= cumsum[i]) {
return i;
}
}
}
int mutate_and_advance(double array[32]) {
double gapped[32];
float chosen_prob;
int bit = choose_bit(array);
create_gapped_array32(gapped, bit);
chosen_prob = array[bit];
array[bit] = 0;
multiply_array_by_scalar(gapped, chosen_prob);
add_32_arrays(array, gapped, array);
return bit;
}
我认为以上就是我所需要的。它现在返回一个int，所以我可以测试它是否按我想要的方式循环遍历索引。
下面的辅助函数和库，以及(非常)粗略的测试:
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
void create_array32(double array[32]) {
int i;
for (i = 0; i < 32; i++) {
array[i] = ldexp(1, -(32 - i));
}
}
void create_gapped_array32(double array[32], int location) {
int i;
for (i = 0; i < 32; i++) {
if (i == location) {
array[i] = 0;
} else {
array[i] = ldexp(1, -(32 - i));
}
}
}
void compute_cumulative_sum(double arr[32], double sum[32]) {
sum[0] = arr[0];
for (int i = 1; i < 32; i++) {
sum[i] = sum[i - 1] + arr[i];
}
}
void multiply_array_by_scalar(double array[32], double scalar) {
int i;
for (i = 0; i < 32; i++) {
array[i] *= scalar;
}
}
void add_32_arrays(double left[32], double right[32], double output[32]) {
int i;
for (i = 0; i < 32; i++) {
output[i] += left[i] + right[i];
}
}
// Test
int main() {
int k = 0;
double probabilties[32] = { 0 };
create_array32(probabilties);
for (k = 0; k < 55; k++) {
printf("Index: %dn", mutate_and_advance(probabilties));
}
return 0;
}