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

[g0blinish]

нужна процедура, ну или проверенная.

[lvd]

Code: Select all

RND   LD H,'RND_TBL
         LD A,0
         INC A
         LD (RND+3),A
         LD L,A
         LD B,(HL)
         ADD A,55-24
         LD L,A
         LD C,(HL)
         ADD A,24
         LD L,A
         LD A,B
         ADD A,C
         LD (HL),A
         RET


требует инициализации таблицы хотя бы одним ненулевым значением, а чтоб выдавались рандомы, надо его по этой таблице прогнать неско сотен раз (если в ней был один неноль -- то больше). В качестве профита -- ниибацо длинный период.

[CHRV]

А вам собственно для чего?
LVD а ты на XOR и сдвиге не делал ГПСЧ? Классический
Кстате таблицо полиномов в руко: http://web.eecs.utk.edu/~plank/plank/pa ... -table.txt

[lvd]

LVD а ты на XOR и сдвиге не делал ГПСЧ? Классический

Если приглядишься, то мой код как раз и есть ксор и сдвиг -- в младших битах. А за счёт старших получается опупенный период.
А ещё люблю такой генератор делать в фпгашках -- можно зажрать всё место очень легко :-D

upd: хренератор на ксор-сдвиге сам по себе может применяться только для случайных битов, число от него -- последовательные его биты с сильной корреляцией и юзать такое низя. Лучше делать A*X+B mod M.

[fk0]

Для этого два генератора смешиваются с разными периодами. У maxim аппнота была.

[fk0]

Можно её на хешах, как в прикладной криптографии Шнайера предлагалось. Но считается медленно.

[lvd]

Для этого два генератора смешиваются с разными периодами. У maxim аппнота была.

Для чего?

[fk0]

Чё??? Смотри... работает только в xterm. ЧЯДНТ? Все методы дают нормальную последователность, кроме A*X+B mod M. (A, B и M взял из wikipedii, там написано, из numerical recipes in C) Собственно из NR in C взял другой такой же тупейший метод -- всё ок.

Code: Select all

/* 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>

#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;
}


#ifdef RANDOM_TEST
#include <stdio.h>

unsigned long govnonext=1;

long int govnorand(void) {
   govnonext=govnonext*1103515245 + 12345;
   return (unsigned int)(govnonext/65536)%32768;
}


int main()
{
   random_init();
   #if 0
   n=65536; do {
      random_feed(n);
      printf("%lu\n", random_get()&0xffff);
      printf("%lu\n", random_get()>>16);
   } while (--n);

   #else

   srand(time(NULL));
   random_feed(rand());

   fputs("\033[?38h\033\014", stdout);
   fflush(stdout);
   putchar(034);
   for (unsigned long i=0; i<200000; i++) {
      unsigned x, y;
      #ifdef RAND
      x=1024.0*rand()/RAND_MAX;
      y=760.0*rand()/RAND_MAX;
      #elif defined(BADRAND)
      x=rand()%1024;
      y=rand()%760;
      #elif defined(RANDOM)
      x=1024.0*random()/RAND_MAX;
      y=1024.0*random()/RAND_MAX;
      #elif defined(LFSR)
      x=random_get()%1024;
      y=random_get()%760;
      #elif defined(BADLFSR)
      x=shift(&lfsr32, PMASK32, 0) % 1024;
      y=shift(&lfsr32, PMASK32, 0) % 760;
      #elif defined (GOVNO)
      #if 0
      static unsigned long A=1664525, C=1013904223, X=54353;
      X=(X*A+C)^0xffffffff;
      x=X%1024;
      X=(X*A+C)^0xffffffff;
      y=X%760;
      #else
      x=govnorand()%1024;
      y=govnorand()%760;
      #endif
      #else
      #error define BADRAND, RANDOM, LFSR, BSDLFSR or GOVNO
      #endif
      putchar(0x20 | (y>>5)), putchar(0x60 | (y&0x1f));
      putchar(0x20 | (x>>5)), putchar(0x40 | (x&0x1f));
   }
   fputs("\033\003", stdout);
   #endif
   return 0;
}
#endif




[lvd]

Все методы дают нормальную последователность, кроме A*X+B mod M

Ты прежде чем такое говорить хотя бы кнута почитай, где он про генераторы пишет. А то смешно выглядит. "взял из википедии"...

[g0blinish]

взял старый, беспонтовый:

Code: Select all

random  PUSH BC:LD A,(R1),C,A
        LD A,(R2):ADD A,C:LD C,A
        LD (R1),A,A,(R3)
        SUB C:LD C,A,(R2),A
        RRCA:LD (R3),A
        LD A,C:POP BC
        RET

R1      DB #15
R2      DB #70
R3      DB #FD

грешил на него, но ошибка была в алгоритме.