范围内的恒定时间随机数

我有一个随机数发生器，它在恒定时间内运行。范围内的恒定时间随机数

原型此功能如下：

uint8_t rand();

我希望能够做的就是创建一个随机返回一个uint8_t使得输出为0，最大值之间的函数，其中最大的是最大数量要退回。这种功能的原型将是：

uint8_t randi(uint8_t max);

有算法在线做这个和堆栈溢出。例如，https://stackoverflow.com/a/6852396/1444313。但我的问题是我想要在不变的时间内实现这一目标。我找不到在任何时间都能做到的任何方法。

此外，我在没有硬件划分的ARM Cortex-m0上运行，因此使用％运算符是不可能的。

有没有人有任何建议或指示我如何实现这一点在恒定时间？

感谢

来源

2017-03-17 Dave_Peachy

我没有看到问题，任何远程合理的恒定长度整数的软件划分实现将具有恒定的时间复杂度。常数因子可能比替代品要高一些，其中最简单的解决方法是颠倒过程并乘以'max'，然后除以常量'MAX'（如果需要，以uint64_t精度）。好处是，在最坏的情况下，由常量划分可以很容易地被优化成编译器的直接乘法/移位/添加序列，或者如果您不信任优化器，则可以通过手动优化。 – doynax

强制性xkcd链接：https：// xkcd。com/221/ – pmg

@doynax我不确定我是否从你的解释中理解了你的方法，如果你认为这可行，你能写一个答案吗？谢谢。 –

为了帮助澄清OP困境，下面是两个简单的解决方案，不符合OP的目标。

什么不工作：

非均匀分布，除非max +1是2

uint8_t randi_fail1(uint8_t max) { 
    return rand()%(max + 1); 
}

均匀分布的功率，而不是统一的时间。

uint8_t randi_fail2(uint8_t max) { 
    unsigned n = (256/(max+1))*(max+1); 
    unsigned r; 
    do { 
    r = rand(); // 0 - 255 
    } while (r >= n); 
    return r/(max+1); 
}

来源

2017-03-17 18:59:37 chux

我之前就犯了非均匀分布问题。易陷入陷入困境，并确保你有100％的统一分配令人惊讶的棘手。 –

这是一个解决方案，可以满足您的要求，但可能不喜欢！

使256个或65536的随机值的255个阵列，称之为uint8_t randval[255][256];

现在每个randval[N][M] <= N;换句话说，子阵列专用于参数randimax。

uint8_t randi(uint8_t max) 
{ 
    return (max == 0u) ? 0u : randval[max - 1][rand()]; 
}

注意randval可以在编译时来构造，或者通过@Realtime里克多维的建议可以在后台进行更新。当然，如果在编译时构建，它可以是const，并存储在闪存中。

来源

2017-03-17 21:20:59

嘿，谢谢你的回复。我在ARM Cortex-m0上，它具有4k内存和32k闪存，我认为我不适合那里！ –

输入和输出都是8位字节，所以为什么不把你的随机值乘以你的'最大值'，然后右移8除以256？我这样做是通过获得一个0-25的随机字母（8位随机，乘以26，取顶部字节）。

来源

2017-03-18 14:48:39 Mike

我不认为这给出了一个统一的分布。 –

范围内的恒定时间随机数

回答

相关问题