pseudocodigo - ¿Qué algoritmos comunes se usan para el rand de C()?

libros de algoritmos pdf

Question

Entiendo que la especificación C no proporciona ninguna especificación sobre la implementación específica de rand() . ¿Qué algoritmos diferentes se usan comúnmente en las diferentes plataformas principales? ¿Cómo difieren?

Answer 1

El campo de los PRNG (Pseudo Random Number Generators) es bastante amplio.

Antes que nada hay que entender que sin tener una entrada externa (generalmente física) no se puede obtener una fuente real de números aleatorios. Por eso estos algoritmos se llaman pseudoaleatorios : generalmente usan una semilla para inicializar una posición en un secuencia muy larga que parece aleatoria pero no es aleatoria en absoluto.

Uno de los algoritmos más simples es el Generador congruente lineal ( LCG ), que tiene algunas restricciones de costo para garantizar una secuencia larga y no es seguro en absoluto.

Otro gracioso (al menos para el nombre) es el Blum Blum Shub Generator ( BBS ) que es inusual para los PRNG normales porque depende de la exponenciación en el módulo aritmético dando una seguridad comparable a otros algoritmos como RSA y El Gamal al romper la secuencia ( también si no estoy seguro de la prueba de ello)

Answer 2

Puede usar la biblioteca Boost Random para diferentes generadores de números aleatorios, si necesita algo específico o más avanzado.

La documentación de Boost Random está here .

Answer 3

Una vez escribí un informe sobre CRNG para un curso en Matemáticas Discretas. Para ello, desensamblé rand () en msvcrt.dll:

msvcrt.dll:77C271D8 mov     ecx, [eax+14h]
msvcrt.dll:77C271DB imul    ecx, 343FDh
msvcrt.dll:77C271E1 add     ecx, 269EC3h
msvcrt.dll:77C271E7 mov     [eax+14h], ecx
msvcrt.dll:77C271EA mov     eax, ecx
msvcrt.dll:77C271EC shr     eax, 10h
msvcrt.dll:77C271EF and     eax, 7FFFh

Entonces, es un LCG algo así como (no probado) ...

int ms_rand(int& seed)
{
  seed = seed*0x343fd+0x269EC3;  // a=214013, b=2531011
  return (seed >> 0x10) & 0x7FFF;
}

Answer 4

Vea este artículo: http://en.wikipedia.org/wiki/List_of_random_number_generators

Este es el código fuente del rand() de glibc rand() :

/* Reentrant random function from POSIX.1c.
   Copyright (C) 1996, 1999, 2009 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Contributed by Ulrich Drepper <[email protected]>, 1996.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <stdlib.h>


/* This algorithm is mentioned in the ISO C standard, here extended
   for 32 bits.  */
int
rand_r (unsigned int *seed)
{
  unsigned int next = *seed;
  int result;

  next *= 1103515245;
  next += 12345;
  result = (unsigned int) (next / 65536) % 2048;

  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;

  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;

  *seed = next;

  return result;
}

Fuente: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/rand_r.c;hb=HEAD

Como puede ver, simplemente se multiplica con una adición y un cambio. Los valores se eligen cuidadosamente para garantizar que no se repita la salida de las iteraciones RAND_MAX.

Tenga en cuenta que esta es una implementación anterior que ha sido reemplazada por un algoritmo más complejo: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/random_r.c;hb=HEAD

Si el enlace está roto, busca "glibc rand_r"