Посоветуйте кошерный Random

Programs, sources, embedded, demomaking, whatsoever related to subj :)

Postby lvd » 27 Nov 2012, 14:28

CHRV wrote:Дык потому и спрашивал "для чего". Городить огуенный период иногда смысла нет.
ПО упрощенке Галуа LFSR тройка операций усе (XOR один раз).
И про кореляции чето не понял, обычно случайное значение в качестве начального ставицо (ну например рефреш регистер)

Не, идико читай Кнута. Во 2ом томе там овер дохуя всего про рнг и методы их тестирования. Я в методы тестирования не вникал, но рекомендации по конкретным рнг старался запомнить. В частности, по юзанию лфср для генерации случайных слов.
F̞͖̭̿̔ͯu̐̅cͬ̑ͩk̨̤̳͇̮̭̪̠̽̿̓̆ͭͩ ̷̩̰͎̩͓̘̾̀ͬ̊ͭ͛ͅda̝̺͙̬͎̝̾͟ ̰̜̝̯͉̯̖̓̎́ͨ̽ͫ͟f̟͇̭̀ͬͨͭ̐̚u̹̼̹̗̞͑̔͂͐̚cͭ̅̊̆̒̆ǩ̝̩̯́ͥ̔̍̑ḭ͓͍̳̬ͦ̽͂n͍͎͈̈̅ͩͬ ̊ͫ̂̾̑̈́f̲͚͉͓͗̋́ͧͦ̅ȗ͇̲̻͈̲̅̎͗͒ͭ͡c̬̟̠̹̯̈́ͩ͘ͅk̫̠̻̋͜a̲͒̾̇!͙͕̺͉̗̩̲̂̏̄̀
User avatar
lvd
 
Posts: 7262
Joined: 07 Apr 2007, 21:28
Group: Registered users

Postby fk0 » 27 Nov 2012, 16:38

Ты говоришь RND хуёвый. Но методики тестирования, почему он хуёвый, привести не можешь (как бы голословно весьма). Я тебе исходник на то дал. Доморощенные RND обычно заливают экран полосками. Что прекрасно видно на примере алгоритмов RANDU и LFSR (хуёвый). Другие алгоритмы дают более вменяемое распределение. Хотя по экрану это, конечно, однозначно можно сказать, что алгоритм плохой, но нельзя сказать что хороший. И видно, например, что два LFSR по методике им Maxim -- всё чётко.

Про LCG (линейный, конгруэнмтный... в твоём понимании Xi+1=(Xi*A+B) MOD M может давать весьма неприятные результаты при плохих A, B и M, так и при малом периоде... Коэффициенты в данном случае взяты натурально из Numerical recipes in C, заглянул не поленился, хуй на википедию.

Обновлённый исходник (сохранить в файл и запускать как ./random.c):
Code: Select all
#! /bin/sh -e
sed -n -e '4,$p' < "$0" | /usr/bin/gcc -x c -std=gnu99 -Wall -O2 -o "$0.$$.out" -
(exec -a "$0" $0.$$.out "$@"); s="$?" ; rm $0.$$.out ; exit $s
/* vim: set foldmethod=marker foldmarker={{{,}}}: */
/* (C) Kirill Frolov (fk0.pp.ru) 2012 */

/* !\file random.c  LFSR pseudo random generator,
*    see: http://www.maxim-ic.com/app-notes/index.mvp/id/4400 */

#include <stdint.h>
//#include "random.h"
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <unistd.h>
#include <strings.h>
#include <signal.h>

#define PMASK32 0xB4BCD35C
#define PMASK31 0x7A5BC2E3

#ifndef PERSISTENT
#define PERSISTENT(v) v
#endif

PERSISTENT(static uint_fast32_t lfsr32);
PERSISTENT(static uint_fast32_t lfsr31);

static unsigned shift(uint_fast32_t *lfsr, uint_fast32_t mask, uint_fast8_t xor)
{
   uint_fast8_t fb = (*lfsr ^ xor)&1;
   *lfsr>>=1;
   if (fb) *lfsr^=mask;
   return *lfsr;
}

static unsigned rand_16(void)
{
   shift(&lfsr32, PMASK32, 0);
   return (shift(&lfsr32, PMASK32, 0) ^ shift(&lfsr31, PMASK31, 0)) & 0xffff;
}

unsigned long random_get(void)
{
   return rand_16()<<16 | rand_16();
}

void random_feed(unsigned r)
{
   do {
      r=r*31153;
      shift(&lfsr32, PMASK32, r>>8);
      shift(&lfsr31, PMASK31, r>>9);
   } while (lfsr31==0 || lfsr32==0); /* avoid zeroizing LFSR */
}

void random_init(void)
{
   if (lfsr32==0) lfsr32=0xABCDE;
   if (lfsr31==0) lfsr31=0x23456789;
}

/********** END OF FK0 RANDOM ********************************************/



void plot_test(int (*func)(void))
{
int Break=0;
   signal(SIGINT, ({void catch(int signo) {
         Break=1;
      }; catch;}));
   setvbuf(stdout, NULL, _IOFBF, 16384);  /* don't hang xterm */
   puts("Press Ctrl-C to exit (screen will be cleared)");
   fputs("\033[?38h\033\014\033\003", stdout), fflush(stdout);
   fputs("\033[?38h", stdout);
   for (unsigned long i=0; i<120000; i++) {
      unsigned x, y;
      x=(unsigned)func() % 1020;
      y=(unsigned)func() % 760;
      //fputs("\033[?38h", stdout);
      putchar(034);
      putchar(0x20 | (y>>5)), putchar(0x60 | (y&0x1f));
      putchar(0x20 | (x>>5)), putchar(0x40 | (x&0x1f));
      putchar(037);
      //fputs("\033\003", stdout);
      if (!(i%4096)) {
         fflush(stdout); /* буханка, буханка! */
         usleep(20000);  /* xterm не успевает */
      }
      if (Break) break;
   }
   puts("\033\003Ok."), fflush(stdout);
   pause();
   fputs("\033[?38h\033\014\033\003", stdout), fflush(stdout);
}


/** really bad random number generator */
unsigned long lcg_next=1;
int LCG(void) {
   lcg_next=lcg_next*1103515245 + 12345;
   return (unsigned int)(lcg_next/65536)%32768;
}


/* RANDU method */
unsigned long randu_x=1;
int RANDU(void) {
   return randu_x=(65539*randu_x)&2147483647;
}

/* libc rand() */
int RAND(void) {
   return rand();
}

/* libc random() */
int RANDOM(void) {
   return random();
}

/* my random method */
int FK0(void) {
   return random_get();
}

/* single LFSR */
int LFSR(void) {
   return shift(&lfsr32, PMASK32, 0);
}

struct method {
   const char *name;
   int (*func)(void);
   const char *comment;
} methods[] = {
#define S(n) #n
#define M(n, c) { S(n), n, c }
   M(RANDU, "well known bad method"),
   M(RAND, "libc rand()"), M(RANDOM, "libc random()"),
   M(LCG, "LCG from NR in C"),
   M(FK0, "Two LFSR mixed"),
   M(LFSR, "Single LFSR (defective)")
#undef M
#undef S
};


int main(int argc, char *argv[])
{
   if (argc!=2) {
      fprintf(stderr, "usage: %s <method>\n", argv[0]);
      fputs("Methods:\n", stderr);
      for (unsigned n=0; n<sizeof(methods)/sizeof(methods[0]); n++)
             fprintf(stderr, "%s \t%s\n", methods[n].name,
            methods[n].comment!=NULL ? methods[n].comment : "");
      fputs("Redirect output to file for raw data.\n", stderr);
      exit(1);
   }

   struct method *method=NULL;
   for (unsigned n=0; n<sizeof(methods)/sizeof(methods[0]); n++)
      if (!strcasecmp(argv[1], methods[n].name)) {
         method=&methods[n]; break;
      }
   if (!method)
      fprintf(stderr, "unknown method: %s\n", argv[1]), exit(1);
   
   random_init();
   srand(time(NULL));
   random_feed(rand());

   if (isatty(fileno(stdout))) {
      printf("Using method: %s\n", method->name);
      plot_test(method->func);
   }
   else {
      fprintf(stderr, "Using method: %s\n", method->name);
      for (unsigned long n=0; n<1000000; n++)
         printf("%u\n", method->func());
   }
   return 0;
}   
* Origin: зип файл! (2:5030/1559)
User avatar
fk0
 
Posts: 1535
Joined: 07 Apr 2007, 01:08
Group: Registered users

Postby fk0 » 27 Nov 2012, 16:39

Ещё прогоню все rand через diehard, но это ждать несколько часов нужно.
* Origin: зип файл! (2:5030/1559)
User avatar
fk0
 
Posts: 1535
Joined: 07 Apr 2007, 01:08
Group: Registered users

Postby CHRV » 27 Nov 2012, 18:17

Пилять трололо это все, хорошесть или хуевость зависит от задачи для чего алгоритм применяется. Вот там хуевость и будет заметна или не заметна. И нет смысла делать многопрходный алгоритм для какойнить тривиальной задачи.
Last edited by CHRV on 27 Nov 2012, 18:18, edited 1 time in total.
Многое есть здесь: www.nedopc.com
User avatar
CHRV
Желесяка
 
Posts: 2136
Joined: 15 Apr 2007, 21:52
Group: Registered users

Postby g0blinish » 27 Nov 2012, 18:17

CHRV wrote:Вот там хуевость и будет заметна или не заметна.

чо я и говорил. не трололо.
User avatar
g0blinish
долбоёб-гумасек
 
Posts: 845
Joined: 31 Oct 2012, 06:21
Group: Registered users

Postby lvd » 27 Nov 2012, 18:33

fk0 wrote:Ещё прогоню все rand через diehard, но это ждать несколько часов нужно.

Дай ссылочку на дайхард.
CHRV wrote:Пилять трололо это все, хорошесть или хуевость зависит от задачи для чего алгоритм применяется.

Ок, так и запишем, со слов ЧРВ, Кнут -- это трололо...
F̞͖̭̿̔ͯu̐̅cͬ̑ͩk̨̤̳͇̮̭̪̠̽̿̓̆ͭͩ ̷̩̰͎̩͓̘̾̀ͬ̊ͭ͛ͅda̝̺͙̬͎̝̾͟ ̰̜̝̯͉̯̖̓̎́ͨ̽ͫ͟f̟͇̭̀ͬͨͭ̐̚u̹̼̹̗̞͑̔͂͐̚cͭ̅̊̆̒̆ǩ̝̩̯́ͥ̔̍̑ḭ͓͍̳̬ͦ̽͂n͍͎͈̈̅ͩͬ ̊ͫ̂̾̑̈́f̲͚͉͓͗̋́ͧͦ̅ȗ͇̲̻͈̲̅̎͗͒ͭ͡c̬̟̠̹̯̈́ͩ͘ͅk̫̠̻̋͜a̲͒̾̇!͙͕̺͉̗̩̲̂̏̄̀
User avatar
lvd
 
Posts: 7262
Joined: 07 Apr 2007, 21:28
Group: Registered users

Postby fk0 » 27 Nov 2012, 20:09

В гугле смотри. Предварительный результат -- только генератор из двух LFSR прошёл частично тесты. Остальные всё провалили. Завтра дам ссылки на результаты теста.

Одиночный (не двойной) LFSR:
Image

RANDU:
Image
* Origin: зип файл! (2:5030/1559)
User avatar
fk0
 
Posts: 1535
Joined: 07 Apr 2007, 01:08
Group: Registered users

Postby CHRV » 27 Nov 2012, 20:17

lvd wrote:Ок, так и запишем, со слов ЧРВ, Кнут -- это трололо...

Гыыыы, типо "не читал но осуждаю"...
Кнут четкий парень, а Пряник еще лучшее.

Я о том что тема сама тупое трололо, если не определено для чего ГСЧ применятьсо бует.
Многое есть здесь: www.nedopc.com
User avatar
CHRV
Желесяка
 
Posts: 2136
Joined: 15 Apr 2007, 21:52
Group: Registered users

Postby CHRV » 27 Nov 2012, 20:21

fk0 wrote: Предварительный результат -- только генератор из двух LFSR прошёл частично тесты. Остальные всё провалили. Завтра дам ссылки на результаты теста.

Ты лучше приведи параметры че за полином, че за алгоритм, а то параметры "LFSR (хуевый)" мне например не понятны.
Многое есть здесь: www.nedopc.com
User avatar
CHRV
Желесяка
 
Posts: 2136
Joined: 15 Apr 2007, 21:52
Group: Registered users

Postby fk0 » 27 Nov 2012, 20:38

Исходник выше. Но думается, полином не шибко важен, если только не очень длинным сделать, что практически сложно.
* Origin: зип файл! (2:5030/1559)
User avatar
fk0
 
Posts: 1535
Joined: 07 Apr 2007, 01:08
Group: Registered users

PreviousNext

Return to Coding

Who is online

Users browsing this forum: No registered users and 1 guest

cron