C Dili rand() Gerçekleştirimi İçin Algoritmalar

rand Gerçekleştirimi Nasıldır?
rand() metodunun hangi algorirtmayı kullanıdığı tanımlı değil. Açıklaması şöyle.

the C rand method is not stable (because the algorithm it uses is unspecified),

Örnek
ISO/IEC 9899:1990 C standard'ındaki örnek şöyle

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
  next = seed;
}

Örnek - Linear congruential generator
Şöyle yaparız.

unsigned int seed = 2;

unsigned int rand()
{
   seed = 1664525 * seed + 1013904223;
   return seed;
}

void srand(unsigned int new_seed)
{
   seed = new_seed;
}

Örnek - Linear congruential generator
Windows'taki gerçek kod şöyledir.

static UINT32 next = 1;

int __cdecl rand(void)
{
    next = next * 1103515245 + 12345;
    /* return (unsigned int)(next / 65536) % 32768;*/
    return (UINT32)(next>>16) & RAND_MAX;
}

void __cdecl srand(unsigned int seed)
{
    /* And you *should* get a warning if sizes dont match
     */
    next = seed;
}

Örnek
xorshift şöyledir

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

Örnek - MacOs
MacOS'taki gerçek kod şöyledir.

/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if (*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));

Açıklaması şöyle.

This does indeed result in all numbers between 1 and RAND_MAX, inclusive, exactly once, before the sequence repeats again. Since the next state is based on multiplication, the state can never be zero (or all future states would also be zero). Thus the repeated number you see is the first one, and zero is the one that is never returned.

C Dili rand metodu - Kullanmayın

Giriş
C ile srand() ve rand() metodları kullanılarak rastgele sayılar üretilebilir. Üretici ilklendirmek için srand() metodu yazısına bakabilirsiniz.

rand artık kullanılmamalı
Açıklaması şöyle.

Use of rand therefore continues to be non-portable, with unpredictable and oft-questionable quality and performance.

rand ve global state
rand() metodu global state kullanır. Bu yüzden önceden belirlenmiş bir diziye ihtiyacımız varsa kesinlikle kullanılmamalıdır.

rand Gerçekleştirimi Nasıldır?
rand() Gerçekleştirimi İçin Algoritmalar yazısına taşıdım.

Aynı Sayı Tekrar Üretilebilir mi ?

Sorunun cevabı evet.

Örnek
Şöyle yaparız

assert(rand() != rand());

Bu kodda koşulunun sağlanmadığı görülebilir.

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

int main(int argc, char* argv[])
{
  unsigned int i;
  for(i = 0; ; i++) {
    int r = rand();
    if (r == rand()) {
        printf("Oops. rand() = %d; i = %d\n", r, i);
        break;
    }
  }
  return 0;
}

Örnek
rand()'ın ne kadar çift sayı ürettiğini görmek için şöyle yaparız

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

int main() {
  size_t size = ((size_t)RAND_MAX) + 1;
  char *randoms = calloc(size, sizeof(char));
  int dups = 0;
  srand(time(0));
  for (int i = 0; i < RAND_MAX; i++) {
    int r = rand();
    if (randoms[r]) {
      // printf("duplicate at %d\n", r);
      dups++;
    }
    randoms[r] = 1;
  }
  printf("duplicates: %d\n", dups);
}

rand() ne Döndürür

rand() metodu genellikle 15 bitlik sayılar üretir. 15 bit olması garanti değildir. Bu yüzden RAND_MAX macrosunu kullanmak gerekir. Yani rand() 0 - RAND_MAX arasında bir sayı üretir, negatif sayı üretmez.

RAND_MAX'ın en az 32767 değerine eşit olması garanti edilmiştir. Windows üzerinde RAND_MAX 32767 (5 haneli rakam) değerine eşittir. Linux üzerinde ise 2147483647 (10 haneli rakam) değerine eşittir.

How to store a random number into a null-terminated character array? sorusunda uzunluk farkına dikkat çekiliyor.

rand() Thread Safe Midir ?
Posix sistemlerde rand() meteodu thread-safe değildir.

The function rand() is not reentrant or thread-safe, since it uses hidden state that is modified on each call.

Bu yüzden aşağıda anlatılan rand_r() metodunu (bilinçsiz kullanılırsa yine thread-safe olmaz!) kullanmak gerekir.Windows'ta ise rand_s()'i kullanmak gerekir.

Üretilen Sayı Dağılımı Nasıldır?
Bir diğer önemli nokta ise rand() Uniform Distribution (tek düze dağılım) sayı üretir. Bir üretecin Uniform Distribution olduğunun nasıl ispatlandığını anlamak için buraya göz atabilirsiniz
.
Dağılım Sınıfları Var Mıdır?
Dağılımı ayarlamak için bir çok kütüphane dağılım sınıfları sunmakta. Maalesef C kütüphanesinde dağılım sınıfı yok.

Dağılımda Bias'a Dikkat
Şu kod tavsiye edilmiyor. Bu tarz kodlar yerine std::uniform_int_distribution sınıfını kullamak daha iyi.

int x = 7;
while(x > 6) 
  x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

Uniform Real Distribution
Şöyle yaparız.

double probability = (rand()/(double)(RAND_MAX + 1));

Ağırlığa Göre Dağılım
Örnek
Şöyle yaparız. %33 oranında BLUE, %66 oranında ise WHITE çıkan bir dağılım var. rand() %3 [0,2] arasında bir değer döner. 0 gelirse (%33) BLUE, 1 ve iki gelirse (%66) oranında WHITE döner.

#define BLUE 1
#define WHITE 2

int whichBall()
{
  int val = rand() % 3;
  if (val == 0)
    return BLUE;
  return WHITE;
}

Örnek
Benzer bir şeyi Java'da şöyle yaparız. 0 - 1000 arasında sayı ütetilir. Bu sayı 10 ile bölünerek 0 - 100 arasına getirilir. %60'ı 0 olur, %40'ı ise 10 ile gölünmüş hali olur.

Stream<Integer> boxed = random.ints(0, 1000).map(r -> r%10 < 6 ? 0 : r/10).boxed();

Random Byte Üretmek
Kriptografik üreteçlerde olduğu gibi random byte üretmek için şöyle yaparız.

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

/* Assumes srand() has been called with an appropriate seed at some point
   Code assumes C99 is available; minor tweaks needed for older compilers.
 */
int gen_random_int() {
  const int BITS_PER_RAND = (int)log2(RAND_MAX + 1);
  int ret = 0;
  for (int i = 0; i < sizeof(int) * CHAR_BIT; i += BITS_PER_RAND) {
    ret <<= BITS_PER_RAND;
    ret |= rand();
  }
  return ret;
}