7

我想收集在一个地方在所有四种类型的间隔上生成随机数的“最佳”方式。我厌倦了谷歌搜索。搜索结果出现了很多废话。甚至相关的结果也是页面或博客,这些页面或博客通常是完全错误的,或者在讨论中自封的专家在某些技术上存在分歧,通常他们的“答案”似乎暴露了他们不了解不同的类型(关闭、开、半开)的区间。对于这样一个“简单”的问题,我厌倦了阅读有关在 C 中生成随机数的不良信息。

请告诉我如何生成均匀分布的浮点数。这是我在 (a,b)、[a,b)、(a,b] 和 [a,b] 上的典型方式(以“long double”为例):

long double a=VALUE1,b=VALUE2;
long double x1,x2,x3,x4;

srand((unsigned)time(NULL));

/* x1 will be an element of [a,b] */
x1=((long double)rand()/RAND_MAX)*(b-a) + a;

/* x2 will be an element of [a,b) */
x2=((long double)rand()/((long double)RAND_MAX+1))*(b-a) + a;

/* x3 will be an element of (a,b] */
x3=(((long double)rand()+1)/((long double)RAND_MAX+1))*(b-a) + a;

/* x4 will be an element of (a,b) */    
x4=(((long double)rand()+1)/((long double)RAND_MAX+2))*(b-a) + a;

对于单位区间 (0,1)、[0,1)、(0,1] 和 [0,1] 的特殊情况:

long double x1,x2,x3,x4;

srand((unsigned)time(NULL));

/* x1 will be an element of [0,1] */
x1=((long double)rand()/RAND_MAX);

/* x2 will be an element of [0,1) */
x2=((long double)rand()/((long double)RAND_MAX+1));

/* x3 will be an element of (0,1] */
x3=(((long double)rand()+1)/((long double)RAND_MAX+1));

/* x4 will be an element of (0,1) */    
x4=(((long double)rand()+1)/((long double)RAND_MAX+2));

我相信对 RAND_MAX 和 rand() 的返回值的强制转换都是必要的,不仅因为我们想要避免整数除法,而且因为它们是整数,否则添加一个(或两个)可能会使它们溢出。

我认为“double”和“float”的版本完全相同,只是替换了类型。不同的浮点类型是否有任何微妙之处?

您发现上述实现有什么问题吗?如果是这样,您将如何解决它以及如何解决它?

编辑:上述实现通过了必要的测试以使其正确(至少在运行 64 位 Linux 的 64 位 Intel Core 2 Duo 机器上):x1 可以生成 0 和 1,x2 可以生成 0 但还没有看到生成 1,x3 可以生成 1,但尚未看到生成 0,并且未看到 x4 生成 0 或 1。

4

5 答案 5

6

如果您希望该范围内的每个双精度值都是可能的,并且概率与它与其相邻双精度值之间的差异成正比,那么它实际上真的很难。

考虑范围[0, 1000]。在该范围的非常小的第一部分中存在绝对的值桶负载:其中有一百万个在0和之间1000000*DBL_MIN,并且DBL_MIN大约是 2 * 10 -308。该范围内总共有多个2^32值,因此显然一次调用rand()不足以生成所有值。您需要做的是均匀地生成双精度数的尾数,并选择一个指数分布的指数,然后稍微捏造一些东西以确保结果在范围内。

如果您要求范围内的每个双精度数都是可能的,那么开放范围和封闭范围之间的差异是相当不相关的,因为在“真正的”连续均匀随机分布中,任何精确值出现的概率无论如何都是 0。因此,您不妨只在开放范围内生成一个数字。

1/(RAND_MAX+1)所有这一切:是的,您提出的实现生成的值在您所说的范围内,并且对于封闭和半封闭范围,它们以概率左右生成端点。这对于许多或大多数实际目的来说已经足够了。

只要在可以准确表示RAND_MAX+2的范围内,您就可以摆弄 +1 和 +2 作品。double这对于 IEEE 双精度和 32 位是正确的int,但 C 标准实际上并不能保证这一点。

(我忽略了你的使用,long double因为它有点混淆了。它保证至少和 一样大double,但是在一些常见的实现中它与 完全相同double,所以long除了不确定性之外不会添加任何东西)。

于 2012-09-07T18:23:53.043 回答
4

此问题尚未准备好回答,因为该问题未完全指定。特别是,没有说明可以生成的值集应该分布到何种程度。为了说明,考虑为 [0, 1] 生成值,并考虑具有可表示值的浮点格式:

0、1/16、2/16、3/16、4/16、6/16、8/16、12/16、1。

这些值的几个分布可能被认为是“均匀的”:

  • 以相等的概率选择每个。这在离散值上是均匀的,但在值之间的实际距离上没有均匀的密度。
  • 选择每个概率与其附近可表示值的密度成正比。
  • 以相等的概率选择 0、4/16、8/16、12/16 和 1,以在区间内保持相同的粒度。

我怀疑其中的第一个是故意的,我会忽略它。第二个类似于 Steve Jessop 的建议,但仍未完全指定。是否应该以与从它到中点到下一个点的间隔成比例的概率选择 0?(这将给出 1/32 的概率。)或者它是否应该与以它为中心的区间相关联,从 -1/32 到 1/32?(这将给它 1/17 的概率,假设 1 也被分配了一个超出其自身 1/32 的间隔。)

您可能会认为这是一个闭区间,因此它应该在 0 和 1 处停止。但假设我们在某些应用程序中将 [0, 2] 上的分布切分为区间 [0, 1] 和 (1, 2]. 我们希望后两个区间上的分布联合等于前一个区间上的分布。所以我们的分布应该很好地啮合。

第三种情况也有类似的问题。也许,如果我们希望保持这样的粒度,应该以 1/8 的概率选择 0,以 1/4 的概率选择 1/4、1/2 和 3/4 这三个点,以 1/8 的概率选择 1 .

除了指定生成器所需属性的这些问题之外,提问者提出的代码还有一些问题:

  • 假设 RAND_MAX+1 是 2 的幂(因此除以它在二进制浮点算术中“很好”),除以 RAND_MAX 或 RAND_MAX+2 可能会导致生成的值出现一些不规则性。其中可能有奇数的量化。

  • 当 1/(RAND_MAX+1) ≤ 1/4 ULP(1) 时,RAND_MAX/(RAND_MAX+1) 将四舍五入并返回 1,因为区间为 [0, 1)。(“ULP(1)”表示正在使用的浮点格式中值 1 的最小精度单位。)(在 RAND_MAX 适合有效数字位的 long double 测试中不会观察到这一点,但是例如,当 RAND_MAX 为 2147483647 且浮点类型为 float,其有效数为 24 位时,就会发生这种情况。)

  • 乘法(b-a)和加法a会引入舍入误差,必须评估其后果。有很多情况,例如何时b-a小而大a,何时跨越零(从而导致 b 附近的粒度损失,即使可以表示更精细的结果)等等。ab

  • (0, 1) 结果的下限是最接近 1/(RAND_MAX+2) 的浮点值。此界限与浮点值的精细度或所需分布无关;它只是rand实现的一个神器。(0, 1/(RAND_MAX+2)) 中的值被省略,没有任何源于问题规范的原因。上端可能存在类似的工件(取决于特定的浮点格式、rand 实现和区间端点,b)。

我提交提问者对这个“简单”问题的答案不满意的原因是它不是一个简单的问题。

于 2012-09-07T19:56:41.713 回答
2

首先,在 [a,b] 上生成随机数。要在 [a,b) 上生成随机数,只需在 [a,b] 上生成一个随机数,检查它是否等于 b,如果是,请重试。对于所有其他开区间变体也是如此。

于 2012-09-07T18:06:18.653 回答
1

在我的脑海中,我只是提供不同浮点和整数类型的所有变体(模板化 C++ 实现的奖励点),我会rand()用更好的东西替换(drand48()想到)

于 2012-09-07T18:10:35.303 回答
0

以下是我用来在生成的数字中查找基本错误的(非常粗略的)测试。这并不是要显示生成的数字是好的,而是它们还不错。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main(int argc, char *argv[]) {

    long double x1,x2,x3,x4;
    if ( argc!=2 ) {
        printf("USAGE: %s [1,2,3,4]\n",argv[0]);
        exit(EXIT_SUCCESS);
    }

    srand((unsigned int)time(NULL));

    printf("This program simply generates random numbers in the chosen interval\n"
               "and looks for values on the boundary or outside it. When an\n"
               "allowable boundary is found, it reports it. Unexpected \"impossible\"\n"
               "values will be reported and the program will terminte. Under\n"
               "normal circumstances, the program should not terminate. Use ctrl-c.\n\n");

    switch ( atoi(argv[1]) ) {
        case 1:
            /* x1 will be an element of [0,1] */
            printf("NOTE: Testing [0,1].\n");
            while ( 1 ) {
                x1=((long double)rand()/RAND_MAX);
                if ( x1==0 ) {
                    printf("x1=0 ENCOUNTERED.\n");
                } else if ( x1==1 ) {
                    printf("x1=1 ENCOUNTERED.\n");
                } else if ( x1 < 0 ) {
                    printf("x1<0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x1 > 1 ) {
                    printf("x1>0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                }
            }
            break;
        case 2:
            /* x2 will be an element of [0,1) */
            printf("NOTE: Testing [0,1).\n");
            while ( 1 ) {
                x2=((long double)rand()/((long double)RAND_MAX+1));
                if ( x2==0 ) {
                    printf("x2=0 ENCOUNTERED.\n");
                } else if ( x2==1 ) {
                    printf("x2=1 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x2 < 0 ) {
                    printf("x2<0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x2 > 1 ) {
                    printf("x2>0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                }
            }
            break;
        case 3:
            /* x3 will be an element of (0,1] */
            printf("NOTE: Testing (0,1].\n");
            while ( 1 ) {
                x3=(((long double)rand()+1)/((long double)RAND_MAX+1));
                if ( x3==1 ) {
                    printf("x3=1 ENCOUNTERED.\n");
                } else if ( x3==0 ) {
                    printf("x3=0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x3 < 0 ) {
                    printf("x3<0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x3 > 1 ) {
                    printf("x3>0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                }
            }
            break;
        case 4:
            /* x4 will be an element of (0,1) */
            printf("NOTE: Testing (0,1).\n");
            while ( 1 ) {
                x4=(((long double)rand()+1)/((long double)RAND_MAX+2));
                if ( x4==0 ) {
                    printf("x4=0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x4==1 ) {
                    printf("x4=1 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x4 < 0 ) {
                    printf("x4<0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                } else if ( x4 > 1 ) {
                    printf("x4>0 ENCOUNTERED. Abnormal termination.\n");
                    exit(EXIT_FAILURE);
                }
            }
            break;
        default:
            printf("ERROR: invalid argument. Enter 1, 2, 3, or 4 for [0,1], [0,1), (0,1], and (0,1), respectively.\n");
            exit(EXIT_FAILURE);
    }

    exit(EXIT_SUCCESS);
}
于 2012-09-07T19:26:30.830 回答