Быстрый (некачественный) рандом

Кнута советовали?

вот тебе самое простое: http://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_comm...

Нужно для создания шума на изображении.

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

Так вот - делать подобные вещи прямо на ходу плохая практика.

вылазь из криокамеры. Сегодня CPU намного быстрее считают, чем память ковыряют.

Linear_congruential_generator
rand

Разве не одно и то же?

я удивлен, что /dev/urandom еще никто не предлагал.

он, кстати не очень быстрый, и слишком хорош для ТСа.

Нравится?

это считать нужно. Вангую, что это у тебя не случайность, а говно.

Черт, а ведь правда жутко медленно!

а ты используй комбинацию вот этого твоего говнеца и какого-то быстрого метода. И получится то, что доктор прописал.

3 58 44

Не благодати.

ВНЕЗАПНО: считать быстрее. Раз так в 50.

При правильном выборе полинома (есть сайты с готовыми оттестироваными полиномами) можно получить хорошую и длинную последовательность.

а теперь посмотри, как оно выглядит на картинке.

зависит от системы. А почему слишком хорош для ТС-а?

их много разных. Посмотри на drand48(3) из glibc. А rand(3) это не лучший выбор.

зависит от системы. А почему слишком хорош для ТС-а?

слишком много случайности и низкая скорость. Во всяком случае в Linux.

У меня проще реализации: если надо очень быстро, использую куду, а если очень случайно — инициализирую периодически ГСЧ "энтропией".

теория без практики мертва

практика без теории слепа.

У тебя второй случай.

Не, у меня шестой.

слишком много случайности

не понял... что?

низкая скорость

а какая скорость - высокая?

$ uname
Linux
$ dd if=/dev/urandom of=file.rnd
^C52864+0 записей считано
52863+0 записей написано
скопировано 27065856 байт (27 MB), 3,74787 c, 7,2 MB/c
$ dd if=/dev/urandom of=/dev/null
^C51768+0 записей считано
51767+0 записей написано
скопировано 26504704 байта (27 MB), 3,39541 c, 7,8 MB/c

$ uname
FreeBSD
$ dd if=/dev/urandom of=file.rnd
^C197924+0 records in
197924+0 records out
101337088 bytes transferred in 3.959385 secs (25594149 bytes/sec)
$ dd if=/dev/urandom of=/dev/null
^C202999+0 records in
202999+0 records out
103935488 bytes transferred in 3.325216 secs (31256765 bytes/sec)

The versions of rand() and srand() in the Linux C Library use the same random number generator as random(3) and srandom(3)

The random() function uses a nonlinear additive feedback random number generator employing a default table of size 31 long integers

а какая скорость - высокая?

У меня rand() выдает примерно 30*10^6 чисел за секунду.

UPD. Ссылки на математическое объяснение генерации случайных чисел и последующее самостоятельное написание функции тоже подходит.

Второй том Кнута?

Второй том Кнута?

У меня время до вечера пятницы. Желательно что то простое для чтения.

чисел в каком диапазоне? с rand() не знаком.

не верю! (c)

У меня время до вечера пятницы. Желательно что то простое для чтения.

Тогда используй самый быстрый из буста:

http://www.boost.org/doc/libs/1_55_0/doc/html/boost_random/performance.html

слишком много случайности

не понял... что?

энтропия — вполне конкретная физическая величина. А rand(3) с лёгкостью прогнозируется. Это очень хорошо видно на картинках, если этот rand(3) нарисовать(просто тупо точками). Т.е. энтропия каждого бита(особенно младших и старших) от rand(3) сильно меньше 1. А вот энтропия /dev/urandom весьма велика, и почти равна 1. Проблема в том, что чем ближе энтропия к 1, тем больше затрачиваемое время. /dev/random даёт биты с энтропией чрезвычайно близкой к 1, но скорость также близка к 0.

а какая скорость - высокая?

root@amilo:~# dd if=/dev/urandom of=/dev/null bs=1M count=64
64+0 записей получено
64+0 записей отправлено
 скопировано 67108864 байта (67 MB), 25,7489 c, 2,6 MB/c
root@amilo:~# time ./a.out >/dev/null 

real	0m9.571s
user	0m9.496s
sys	0m0.056s

#include <stdio.h>
#include <stdint.h>

inline uint32_t rand32()
{
	static uint32_t seed = 1;
	seed *= 1664525u;
	seed += 1013904223u;
	return seed;
}

int main()
{
	uint32_t j;
	for(j = 0; j < 64*1048576; j++)
	{
		uint32_t x = rand32();
		fwrite(&x, sizeof(x), 1, stdout);
	}
	return 0;
}

не верю! (c)

проверяй. А то мне жеж не поверишь...

Забавный заголовок. Дум писали в эмаксе! ))

спасибо за разъяснение, пригодится. Я ранее интересовался генерацией энтропии, но немного в другом плане.
Однако программу я не осилил, ибо пока в изучении Си сижу вот тут

Сколько циклов на генерирование, и сколько циклов на выборку из памяти - приведи цифирь.

у меня вся программа: seed = (1664525 * seed + 1013904223)mod2^32 seed₀ = 1 А считай всё время она проводит заталкивая числа в stdout, потом в bash, а потом в /dev/null.

если без вывода, то 1073741824 чисел создаёт 10.956сек, что при тактовой частоте атома N270 1600мгц составляет 16.33 такта на число.

080482c0 <main>:
 80482c0:	a1 18 97 04 08       	mov    eax,ds:0x8049718
 80482c5:	b9 00 00 00 40       	mov    ecx,0x40000000
 80482ca:	8d b6 00 00 00 00    	lea    esi,[esi+0x0]
 80482d0:	8d 14 00             	lea    edx,[eax+eax*1]
 80482d3:	01 c2                	add    edx,eax
 80482d5:	8d 14 90             	lea    edx,[eax+edx*4]
 80482d8:	c1 e2 08             	shl    edx,0x8
 80482db:	01 c2                	add    edx,eax
 80482dd:	8d 14 92             	lea    edx,[edx+edx*4]
 80482e0:	8d 04 90             	lea    eax,[eax+edx*4]
 80482e3:	8d 04 80             	lea    eax,[eax+eax*4]
 80482e6:	8d 84 80 5f f3 6e 3c 	lea    eax,[eax+eax*4+0x3c6ef35f]
 80482ed:	49                   	dec    ecx
 80482ee:	75 e0                	jne    80482d0 <main+0x10>
 80482f0:	a3 18 97 04 08       	mov    ds:0x8049718,eax
 80482f5:	31 c0                	xor    eax,eax
 80482f7:	c3                   	ret    

А считай всё время она проводит заталкивая числа в stdout, потом в bash, а потом в /dev/null.

ну, эту часть я понял сразу, но вот это:

seed = (1664525 * seed + 1013904223)mod2^32 seed₀ = 1

я либо торможу, либо пора всё-таки начать учить матчасть.

выбрать 32 бита из памяти больше 16 тактов?

выбрать 32 бита из памяти больше 16 тактов?

Тут говорили про кэш промахи из-за этого. В принципе вполне может быть, таблица данных скорее всего будет вне кэша, то есть в оперативе.

Ну, я почти готов признать своё поражение... :)

seed = (1664525 * seed + 1013904223)mod2^32 seed₀ = 1

тут всё просто:

1. сначала seed равно 1. Это жёстко в коде забито(прямо в самом бинарнике)

2. Для генерации каждого числа, мы

2.1 умножаем seed на 1664525

2.2 берём остаток от деления на 2³² (тупо 32 младших бита произведения, остальное выкидываем)

2.3 прибавляем 1013904223

2.4 опять берём остаток от деления на 2³² уже от суммы

2.5 записываем новое число в seed

тут вся магия в константах, которые Кнут получил с помощью лютого матана.

А можно забульбенить аппаратный генератор на дробовом шуме ☺

Воткнуть его в PCI и получать мегашустрый random (хреновый, но зато мегашустрый). Правда, он будет ближе к Пуассону. Но ТСу-то пофиг.

Так нужно же что бы это у всех работало) Я уже думал сделать себе рандом из радиочастот, или чего то подобного.

Распространяй софт вместе с зондом аппаратным генератором шума.

А вообще, нафига оно тебе нужно-то? Вот мне, например, здесь нужен был очень шустрый ГСЧ, чтобы "фотоны бросать" на зеркало.

Вот мне, например, здесь

Мне так лень учится как все это собирать... В суботу вечером гляну.))

выбрать 32 бита из памяти больше 16 тактов?

конечно. Это тебе не L1 и не регистры.

Ну и повторюсь — только мой убогий атом делает умножение на LEA, за ~12 тактов, любой современный процессор одним ядром может за такт 8 чисел помножить сразу, за 1 такт.

https://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод
Cовершенно банальный вариант, причём некачественный.

Воткнуть его в PCI и получать мегашустрый random

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

Правда, он будет ближе к Пуассону.

ну сделай, как Кнут говорит «квадрат»: возведи число в квадрат, и возьми те биты, что посередине. Получится равномерное распределение. Ещё лучше взять текущее число и умножить на прошлое(правда возникает некоторое уменьшение энтропии, но она почти всегда не имеет значения)

Cовершенно банальный вариант, причём некачественный.

после небольшой доработки напильником он становится вполне годным.

энтропия — вполне конкретная физическая величина. А rand(3) с лёгкостью прогнозируется. Это очень хорошо видно на картинках, если этот rand(3) нарисовать(просто тупо точками). Т.е. энтропия каждого бита(особенно младших и старших) от rand(3) сильно меньше 1. А вот энтропия /dev/urandom весьма велика, и почти равна 1. Проблема в том, что чем ближе энтропия к 1, тем больше затрачиваемое время. /dev/random даёт биты с энтропией чрезвычайно близкой к 1, но скорость также близка к 0.

Энтропия бита тут немного не в тему.

int n=some_realy_random_number();
...
int rand(){
    return (n=!n);
}

Энтропия младшего бита равна единице, но генератор отвратительный.

Если качество начинает влиять, то лучше использовать другой тип генераторов.
https://ru.wikipedia.org/wiki/Вихрь_Мерсенна
А именно его SFMT подвид
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
Потому что он ориентирован на 128-битный SIMD. Как бы. Т. е. SSE2, но не SSE. Потому что целочисленный, хотя перейти к float-ам нетяжело. Правда, у него табличка. В общем, много разных «но».

Ясно, спасибо, понял. Ты прав.

return (n=!n); Энтропия младшего бита равна единице, но генератор отвратительный.

Энтропия тут равна НУЛЮ. Энтропия по определению — величина, которая характеризует наше НЕЗНАНИЕ. Например энтропия того, какой стороной выпадет идеальная монетка равна 1 бит. Потому-что мы не знаем, как она упадёт, и имеется два исхода. Т.е. логарифм числа исходов равен 1.

А в твоём генераторе мы ЗНАЕМ, что он выдаст, потому его энтропия нулевая, в точности как и у /dev/zero.

Определить энтропию очень просто: если источник выдал 1000000 бит, надо их все предсказать. Если верно предсказано ½ битов, то энтропия каждого равна 1. А если все — то 0. При этом предполагается, что предсказатель честно играет, и предсказывает будущее, а не троллит. Т.е. нужно набрать Over9000 предсказателей, а потом расстрелять всех кроме того, кто лучше всех предсказал. Очевидно в твоём случае вероятность правильного предсказания равна 1, а значит нужность(энтропия) твоих битов равна 0, т.к. мы их и так можем предсказать.

Если качество начинает влиять, то лучше использовать другой тип генераторов. https://ru.wikipedia.org/wiki/Вихрь_Мерсенна

можно и это конечно. Хотя я думаю, что ТСу хватит и обычного классического генератора, только надо его допилить. Ну к примеру можно хранить с десяток чисел, и в качестве нужного 8и битного числа брать XOR всех 10и чисел. Это позволит избавится от главной болезни линейного генератора: зависимости очередного числа от предыдущего. При этом скорость почти не пострадает: функция XOR обратная к самой себе, потому нужно добавить новое число, и добавить 11ое(которое надо вообще убавить, но для XOR это тоже самое). А если генератор как у меня даёт 32х битные числа, то это 4 восьми битных за раз. Я думаю, 3х тактов ТСу более чем хватит(потому-что ему их всё равно не переварить с такой бешеной скоростью).

Энтропия по определению равна минус сумме p(x) log(p(x)). Априорная вероятность младшего бита равна 1/2 и для 0, и для 1 => энтропия равна 1.

Априорная вероятность младшего бита равна 1/2

как можно считать априорную вероятность известной величины? Давай-как ты азы подучишь...