25 Nisan 2020 Cumartesi

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.


Hiç yorum yok:

Yorum Gönder