Page 2 of 2

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 15:57:10
by VBI
psb, RANDOM - это организатор СС

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 16:01:07
by g0blinish
psb wrote:g0blinish, JP M - это комментарий.


а без комментария?

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 16:36:25
by TS-Labs
VBI, LVD это Low-voltage differential signaling.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 17:40:11
by VBI
TS-Labs, VBI это Vertical Blanking Interval.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 17:48:35
by g0blinish
пиздюки, ответьте на мой ответ!

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 18:24:02
by VBI
отвечает Друзь

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 18:25:48
by introspec
Может хорош фигню-то писать, а, шутники?

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Tue, 01.12.2015 18:27:41
by g0blinish
не, нужно, да.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 18:21:43
by TS-Labs
introspec wrote:Вариант 3: Длина последовательности 224-1, вырожденный полином, время работы 90 тактов (для битов) или 90+11=101 такт (для байтов).

introspec wrote:Вариант 4: Длина последовательности 224-1, полином получше, время работы 106 тактов (для битов) или 106+11=117 тактов (для байтов).

В обоих последовательностях есть места из подряд идущих нулей в количестве до восьми. Как воркэраунд можно написать отлов последовательно одинаковых байт.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 18:44:07
by introspec
Нужно на самом деле поискать более научный способ замешивания байтов. Визуально оба варианта выглядят вполне себе ОК и для 1Д и для 2Д тестов.
Конечно, я думал в первую очередь о скорости.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 18:46:36
by g0blinish
introspec, куда пропал?(:

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 19:08:49
by introspec
Работаю.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 19:10:32
by psb
хороший научный способ (проверенный временем) - десятки раундов нелинейной функции.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 19:13:29
by introspec
"Десятки раундов нелинейной функции" - за 15 или даже 11 тактов?!

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 19:22:08
by TS-Labs
Так, продолжая тему "илитного" генератора (сорри за офтоп), вариант на сях.

Code: Select all
#include <string.h>

u8 seed[4];

void rnd_init(u32 s)
{
  *(u32*)seed = s;
}

u8 rnd()
{
  u8 c;
  c = seed[0] + seed[1] + seed[2] + seed[3];
  c = (c << 1) | ((c >> 7) & 1);
  seed[0] = seed[1];
  seed[1] = seed[2];
  seed[2] = seed[3];
  seed[3] = c;
  return c;
}

void test(u32 s)
{
  u8 t1[sizeof(seed)];
  u32 cyc = 0;
 
  rnd_init(s);
  for (int i = 0; i < sizeof(seed); i++)
    t1[i] = rnd();
 
  while (1)
  {
    rnd();
    cyc++;
    if (!memcmp(t1, seed, sizeof(seed))) break;
  }
 
  printf("Seed: %d, Cycles: %d\n", s, cyc);
}

int main()
{
  int a = 1;

  while (1)
    test(a++);
}


Тест замеряет количество циклов, через которое зацикливается последовательность.
Длина оной зависит от выбранного сида (который не должен быть равен 0).
Цифры неслабые - от 300млн и выше.
Потенциально длину сида можно увеличить с 4 для удлинения цикла.

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 19:29:16
by introspec
Я не понимаю эту вашу страсть к велосипедам. Зачем говнокодить говно, если есть Mersenne Twister?
Давайте всё же перестанем складывать сюда всё напетое Рабиновичем и ограничимся БЫСТРЫМИ генераторами чего-то ПРИЛИЧНОГО.

Для танкистов:
1. БЫСТРОЕ означает не более 110 тактов Z80.
2. ПРИЛИЧНОЕ означает - адекватные результаты в по крайней мере 2х базовых тестах:
  • "1D" заливке экрана подряд созданными байтами
  • "2D" рисовании точек с координатами (раз случайный байт, два случайный байт)

Re: Быстрые генераторы ПСЧ на основе LFSR

PostPosted: Thu, 10.03.2016 19:31:11
by TS-Labs
Хокей, хокей. Спасибо за сцылко )