1

Fiz o seguinte lcg (gerador congruencial linear) para sortear unsigned int de 0x00000000 a 0xFFFFFFFF uniformemente. Só para teste, usei a semente igual a zero e sorteando os cinco primeiros números para ver o que sai.

# include <stdio.h>

unsigned long long int state = 0 ;

unsigned int rnd() {
    state *= 0x60BDC8431972EFA5ull ;
    state += 0x4D268FBC9E53A107ull ;
    return (unsigned int)( state >> 32 ) ;
}

int main(void) {
    printf( "%u\n" , rnd() ) ;
    printf( "%u\n" , rnd() ) ;
    printf( "%u\n" , rnd() ) ;
    printf( "%u\n" , rnd() ) ;
    printf( "%u\n" , rnd() ) ;
    return 0 ;
}

O resultado é esse.

1294372796
3162674411
1090754839
3480286764
3255825657

Para sortear um número em formato single floating point dentro do intervalo [a,b] eu fiz a seguinte função que simplesmente divide o inteiro sorteado por 0xFFFFFFFFu para funcionar como sorteio de 0.0f a 1.0f e usa o resultado para fazer lerp de a a b.

float random( float a , float b ){
    float f0t1 = rnd()/(float)(0xFFFFFFFFu) ;
    return a * ( 1-f0t1 ) + f0t1 * b ;
}

Testando assim,

int main(void) {
    printf( "%f\n" , random(0,1) ) ;
    printf( "%f\n" , random(0,1) ) ;
    printf( "%f\n" , random(0,1) ) ;
    printf( "%f\n" , random(0,1) ) ;
    printf( "%f\n" , random(0,1) ) ;
    return 0 ;
}

o resultado é esse.

0.301370
0.736368
0.253961
0.810317
0.758056

Quer dizer, faz uma divisão que custa muito. Até dá para converter em multiplicação, mas não há um meio mais rápido de calcular isso? Imagino que com números mágicos daria para manusear o código binário do float de maneira eficiente e calcular, correto?

1 Resposta 1

1

Certamente pode-se trocar o typecast do inteiro sorteado e a divisão por duas operações de inteiros e a conversão do código binário. Considerei as otimizações de compilação e aproveitei para fazer passo a passo para ficar claro. Perceba que a impressão com a mesma main é do mesmo resultado.

float random( float a , float b ){
    unsigned int magic = rnd() ;          // Sorteia de 0x00000000 a 0xFFFFFFFF
    magic >>= 9 ;                         // Ficou entre 0x00000000 e 0x007FFFFF
    magic += 0x3F800000 ;                 // Ficou entre 0x3F800000 e 0x3FFFFFFF
    float f1t2 = *(float*)&magic ;        // Magicamente ficou entre 1.00000000 e 1.99999988
    float f0t1 = f1t2 - 0.99999994f ;     // Ficou entre 0.00000006 e 0.99999994
    return a * ( 1-f0t1 ) + f0t1 * b ;    // Finalmente ficou entre "a" e "b"
}

O deslocamento de nove bits para a direita é para abrir espaço para os bits de sinal e expoente do float eliminando os dígitos menos significativos. Pode-se usar magic &= ~0x3F800000 ; também e não sei se impacta no desempenho, mas isso elimina os algarismos mais significativo e o resultado sai diferente.

Bem como a adição do "número mágico" 0x3F800000 (código do 1.0f) é para preencher esses bits. Pode ser uma operação | ao invés de uma soma, não sei se impacta no desempenho mas no resultado não.

Perceba que após a conversão se subtrai não por 0x3F800000 = 1.0f (que faria o resultado ir de 0.00000000 e 0.99999988) mas sim por 0x3F800000 - 1 = 0.99999994f para equilibrar as aproximações das fronteiras.

Suponho que se cogite o retorno de a * ( 2-f1t2 ) + ( f1t2-1 ) * b anulando a necessidade de f0t1, mas imagino que o impacto no desempenho é o mesmo e os arredondamentos tiram o controle das fronteiras.

Agora perceba que embutir "inline" a função rnd pode resultar não só na diminuição no número de chamadas mas também possivelmente na redução de uma operação de inteiro, porém não se sabe pois um shift se faz antes de converter de 64 para 32 bits e a outra depois. Portanto pode-se fazer também o seguinte por garantia.

float random( float a , float b ){
    state *= 0x60BDC8431972EFA5ull ;
    state += 0x4D268FBC9E53A107ull ;
    unsigned int magic = (unsigned int)( state >> (32+9) ) ;
    magic += 0x3F800000 ;
    float f1t2 = *(float*)&magic ;
    float f0t1 = f1t2 - 0.99999994f ;
    return a * ( 1-f0t1 ) + f0t1 * b ;
}

E finalmente perceba que o raciocínio vale para double floating point, afinal é só considerar que são 32 bits sorteados a não ser que mude o lcg (pode até usar os 64 bits gerados, como mostro a seguir), 12 bits de sinal e expoente, o "número mágico" igual a 1.0 é 0x3FF0000000000000 e o subtraendo 0x3FF0000000000000 - 1 magicamente é 0.9999999999999999.

double random( double a , double b ){
    state *= 0x60BDC8431972EFA5ull ;
    state += 0x4D268FBC9E53A107ull ;
    unsigned long long int magic = state >> 12 ;
    magic += 0x3FF0000000000000ull ;
    double f1t2 = *(double*)&magic ;
    double f0t1 = f1t2 - 0.9999999999999999 ;
    return a * ( 1-f0t1 ) + f0t1 * b ;
}

E repare que mais uma vez o resultado impresso é o mesmo.

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 .