3

Preciso gerar um número aleatório baseado em outro número de entrada, de modo que, para o mesmo número de entrada, a função deve sempre gerar o mesmo número de saída.

Por exemplo, meuRand(4) sempre retornaria 236 (ou qualquer outro número), e meuRand(11) sempre retornaria 1747. Não há problema se por acaso meuRand(xx), com xx diferente de 4, também retornasse 236.

Esses valores são só para ilustrar.

Por hora, tenho essa função, que encontrei aqui, devidamente portada para C, como exemplo:

double noise(int x) {
    x = ((x << 13) ^ x);
    x *= x * 15731;
    x += 789221;
    x *= x;
    x += 1376312589;
    x &= 0x7fffffff;
    return 1.0 - ((double)x / 1073741824.0);
}

Essa função retorna valores no intervalo de -1 até 1, mas isso não é problema. O retorno ser um número inteiro ou de ponto flutuante é indiferente.

O objetivo final desses números aleatórios é realmente gerar um mapa com um Perlin Noise 2D. Por isso gostaria de testar meu algoritmo com outra função de geração de números aleatórios, e preferencialmente, que essa função fosse rápida de ser calculada.

Precisa ser um algoritmo, não pode ser algo como utilizar esse esquema em C, para sempre gerar o mesmo número com base no 4, por exemplo:

srand(4);
rand();

pois o código final nem sempre será executado em C, C++, C# etc.

4
  • Pergunta relacionada (não é exatamente uma duplicata, mas algumas respostas lá podem se aplicar aqui)
    – mgibsonbr
    Commented 14/05/2014 às 1:37
  • Oi mgibsonbr! Valeu, eu tinha visto essa pergunta, mas não a primeira resposta. Acho que dá para fazer um teste :) Commented 14/05/2014 às 1:47
  • "O retorno ser um número inteiro ou de ponto flutuante é indiferente." Sugeriria trabalhar sempre com inteiros, para não ter problema se mudar de arquitetura de processador (se for desejado que o mapa seja igual em qualquer máquina). Dependendo do tipo de mapa que fizer, uma diferença de arredondamento ou precisão pode te dar um vale numa máquina e uma colina em outra.
    – Largato
    Commented 16/05/2014 às 13:35
  • Concordo, @Bacco, isso é perigoso em várias aplicações! Mas nesse caso particular, não! Ainda bem ;) Dessa vez, basta que o resultado fique "bonito" e está OK! Commented 16/05/2014 às 13:42

2 Respostas 2

4

A solução mais simples que posso oferecer é usar simplesmente uma função de hash - como o MD5 (ou algo mais sofisticado - embora creio que no seu caso é mais importante que a função seja rápida). Elas oferecem o que você busca (mesma saída para a mesma entrada), são amplamente suportadas por diversos sistemas e linguagens de programação, e são consideradas - em teoria pelo menos (pois servem de base para muitos sistemas criptográficos) - como indistinguíveis na prática de números aleatórios.

E, se o que você quer é uma sequência de números aleatórios - não somente um - ainda é possível utilizar o número original como semente de uma sequência, e a partir daí ir incrementando um contador para gerar o número seguinte (ou qualquer outro depois dele). Ex.:

aleatorio(semente, indice) = MD5(semente + indice)

Outros algoritmos (como alguns propostos numa pergunta relacionada) podem ser ainda mais eficientes, mas se o que se busca é portabilidade eu usaria isso como primeira opção.

2
  • 1
    Realmente, você sacou algo que esqueci de dizer na pergunta... Seria bom que a função fosse rápida :) Vou testar todas as alternativas. Commented 14/05/2014 às 2:00
  • Acabei de encontrar outra forma de gerar esse tipo de número aleatório. Depois dá uma olhada na resposta que acabei de colocar aqui, para compartilhar o conhecimento com o pessoal :) Commented 16/05/2014 às 12:56
2

Acabei de encontrar uma forma de gerar esse tipo de número pseudo-aleatório, criada pelo próprio idealizador do Perlin Noise, Ken Perlin.

Ele deixou um de seus talks disponíveis online aqui. Ao longo da explicação, ele leva para um de seus outros sites, onde mostra o algoritmo original.

Por completude, e pelo fato do algoritmo não ser patenteado/estar disponível online (além de eu já ter feito as devidas referências), vou colocar o algoritmo dele aqui:

/* coherent noise function over 1, 2 or 3 dimensions */
/* (copyright Ken Perlin) */

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

#define B 0x100
#define BM 0xff

#define N 0x1000
#define NP 12   /* 2^N */
#define NM 0xfff

static p[B + B + 2];
static float g3[B + B + 2][3];
static float g2[B + B + 2][2];
static float g1[B + B + 2];
static start = 1;

static void init(void);

#define s_curve(t) ( t * t * (3. - 2. * t) )

#define lerp(t, a, b) ( a + t * (b - a) )

#define setup(i,b0,b1,r0,r1)\
    t = vec[i] + N;\
    b0 = ((int)t) & BM;\
    b1 = (b0+1) & BM;\
    r0 = t - (int)t;\
    r1 = r0 - 1.;

double noise1(double arg)
{
    int bx0, bx1;
    float rx0, rx1, sx, t, u, v, vec[1];

    vec[0] = arg;
    if (start) {
        start = 0;
        init();
    }

    setup(0, bx0,bx1, rx0,rx1);

    sx = s_curve(rx0);

    u = rx0 * g1[ p[ bx0 ] ];
    v = rx1 * g1[ p[ bx1 ] ];

    return lerp(sx, u, v);
}

float noise2(float vec[2])
{
    int bx0, bx1, by0, by1, b00, b10, b01, b11;
    float rx0, rx1, ry0, ry1, *q, sx, sy, a, b, t, u, v;
    register i, j;

    if (start) {
        start = 0;
        init();
    }

    setup(0, bx0,bx1, rx0,rx1);
    setup(1, by0,by1, ry0,ry1);

    i = p[ bx0 ];
    j = p[ bx1 ];

    b00 = p[ i + by0 ];
    b10 = p[ j + by0 ];
    b01 = p[ i + by1 ];
    b11 = p[ j + by1 ];

    sx = s_curve(rx0);
    sy = s_curve(ry0);

#define at2(rx,ry) ( rx * q[0] + ry * q[1] )

    q = g2[ b00 ] ; u = at2(rx0,ry0);
    q = g2[ b10 ] ; v = at2(rx1,ry0);
    a = lerp(sx, u, v);

    q = g2[ b01 ] ; u = at2(rx0,ry1);
    q = g2[ b11 ] ; v = at2(rx1,ry1);
    b = lerp(sx, u, v);

    return lerp(sy, a, b);
}

float noise3(float vec[3])
{
    int bx0, bx1, by0, by1, bz0, bz1, b00, b10, b01, b11;
    float rx0, rx1, ry0, ry1, rz0, rz1, *q, sy, sz, a, b, c, d, t, u, v;
    register i, j;

    if (start) {
        start = 0;
        init();
    }

    setup(0, bx0,bx1, rx0,rx1);
    setup(1, by0,by1, ry0,ry1);
    setup(2, bz0,bz1, rz0,rz1);

    i = p[ bx0 ];
    j = p[ bx1 ];

    b00 = p[ i + by0 ];
    b10 = p[ j + by0 ];
    b01 = p[ i + by1 ];
    b11 = p[ j + by1 ];

    t  = s_curve(rx0);
    sy = s_curve(ry0);
    sz = s_curve(rz0);

#define at3(rx,ry,rz) ( rx * q[0] + ry * q[1] + rz * q[2] )

    q = g3[ b00 + bz0 ] ; u = at3(rx0,ry0,rz0);
    q = g3[ b10 + bz0 ] ; v = at3(rx1,ry0,rz0);
    a = lerp(t, u, v);

    q = g3[ b01 + bz0 ] ; u = at3(rx0,ry1,rz0);
    q = g3[ b11 + bz0 ] ; v = at3(rx1,ry1,rz0);
    b = lerp(t, u, v);

    c = lerp(sy, a, b);

    q = g3[ b00 + bz1 ] ; u = at3(rx0,ry0,rz1);
    q = g3[ b10 + bz1 ] ; v = at3(rx1,ry0,rz1);
    a = lerp(t, u, v);

    q = g3[ b01 + bz1 ] ; u = at3(rx0,ry1,rz1);
    q = g3[ b11 + bz1 ] ; v = at3(rx1,ry1,rz1);
    b = lerp(t, u, v);

    d = lerp(sy, a, b);

    return lerp(sz, c, d);
}

static void normalize2(float v[2])
{
    float s;

    s = sqrt(v[0] * v[0] + v[1] * v[1]);
    v[0] = v[0] / s;
    v[1] = v[1] / s;
}

static void normalize3(float v[3])
{
    float s;

    s = sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
    v[0] = v[0] / s;
    v[1] = v[1] / s;
    v[2] = v[2] / s;
}

static void init(void)
{
    int i, j, k;

    for (i = 0 ; i < B ; i++) {
        p[i] = i;

        g1[i] = (float)((random() % (B + B)) - B) / B;

        for (j = 0 ; j < 2 ; j++)
            g2[i][j] = (float)((random() % (B + B)) - B) / B;
        normalize2(g2[i]);

        for (j = 0 ; j < 3 ; j++)
            g3[i][j] = (float)((random() % (B + B)) - B) / B;
        normalize3(g3[i]);
    }

    while (--i) {
        k = p[i];
        p[i] = p[j = random() % B];
        p[j] = k;
    }

    for (i = 0 ; i < B + 2 ; i++) {
        p[B + i] = p[i];
        g1[B + i] = g1[i];
        for (j = 0 ; j < 2 ; j++)
            g2[B + i][j] = g2[i][j];
        for (j = 0 ; j < 3 ; j++)
            g3[B + i][j] = g3[i][j];
    }
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .