использовать заранее подготовленные случайные числа =)

RdRand от intel

Ты вроде бы игру пишешь. Так вот - делать подобные вещи прямо на ходу плохая практика. К примеру - вычислять синус угла с помощью sin или корень с помощью sqrt. Как можно больше данных подготавливай до игрового цикла (в случае синуса - заранее созданная таблица угол -> значение).

http://www.rand.org/pubs/monograph_reports/MR1418.html

В куде забульбень. УМВР.

Ыщщо вариант: открой /dev/dsp и читай оттуда свой псевдослучайный набор. Но таки с кудой лучше, да и все равно обычно изображения в ней обрабатываются.

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

Шум Перлина нужен тебе.

Быстрее rand()/drand48() навряд ли что-то будет, только разве что заинлайненная реализация похожего алгоритма прямо у себя в коде (в мане написано как оно работает) + использование каждого вызова drand48() сразу для заполнения 4-6 байт.

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

Это делается не любым шумом. Например смотри dithering

Multiply-with-carry?

А откуда в /dev/dsp что-то будет? Уж лучше в кукарекуде

Шумы АЦП.

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

НЕТ, только КУКАРЕКУДА.

Эдди, откуда ты берешь все эти свои шумы? Сделай сам cat /dev/dsp и скажи, что ты видишь

смотри xorshift если хочешь быстрый алгоритм.

qrand()

естественно, он thread local storage использует.

и ты наверное генерируешь число, потом делишь его по модулю на 256? если так, то ты теряешь все биты кроме младших 8 (которые кстати еще и менее случайны в линейном конгруэнтном генераторе). освой битовые операции.

а вот как эта проблема была решена в doom'е: https://github.com/chocolate-doom/chocolate-doom/blob/master/src/doom/m_random.c

НЕТ, только КУКАРЕКУДА.

Да пожалуйста, просто у ТСа может быть какой-нибудь косяк (скажем, говножелезо).

Сделай сам cat /dev/dsp и скажи, что ты видишь

Вот кусок:

00036c0 7e79 9e98 ae95 6077 7a69 ad89 83ac 898c
00036d0 8082 a083 6d81 7597 4e72 6991 adb7 b1bb
00036e0 8cb9 6477 896f e4b9 a6b1 b791 8d69 8892
00036f0 a19c 987c 9f9f afc4 9bc2 6972 9972 a599
0003700 a8b2 e3c3 a2b2 9a88 7f69 6272 a085 a1b2
0003710 526d 3161 6250 4a68 4152 583d 8e76 9c72
0003720 bf9b eab5 b283 437d 9471 9762 c1d6 7b7b
0003730 5c66 b371 5891 5776 977e 71b2 816e ca93
0003740 88a6 a492 7e6f af80 7e7d 8388 c77d 8ed1
0003750 859a cec8 e3b2 5184 7736 969e 673f 1e39
0003760 577c a092 957c 90a2 6a83 c0a3 6a57 245f
0003770 b299 9087 5693 b95d 9d9e 87a8 cfb3 cc6c
0003780 5388 264f 7f6b 4b31 0730 0b0a 1804 2c57
0003790 5d44 2478 a857 8a39 094d 3904 4d3a 7d89
00037a0 6d54 942c 4da1 5c86 8b18 ae89 bbfd aeb4
00037b0 b1aa 4c54 8bb5 a195 b068 5bbe d5ca a2a8
00037c0 b88d c294 aac9 a1c5 99f3 cbb6 bb0d 4589
00037d0 e379 f0a1 5df7 9ecc ff44 5593 016e 7e8c
00037e0 ff3b c98a 7bfe bbdc ba31 71a7 9bae e90e
00037f0 ae90 4df6 a239 6935 2ace 7c0d 848f 6bae
0003800 b4c3 678e 62d3 4c0b d93e 59f4 a78d 819f
0003810 7ec3 257d 7363 e055 8c93 0aac 9395 434b
0003820 8f92 b9f3 d7a2 8d45 51bf 96ea 496d 5c5b
0003830 ca4c 145b b467 6156 6a4d cbb9 c178 05a1
0003840 265d 6f56 17ff de3f b1b5 31b4 dc58 21a4
0003850 6448 98a7 b58a 9363 985c 94d8 7588 afd1
0003860 ffce f8fd b283 dba8 5ba8 67ca 3488 9352
0003870 8c67 784e 01a1 938d 855a a0b5 908a b47d
0003880 9da9 92db 59aa 9be5 64fe f220 c150 9638
0003890 71b2 6624 4949 7b54 5a49 1e35 ca4e ae98
00038a0 797a 272a 6651 4b6b 2557 a88c 895e 9d95

то ты теряешь все биты кроме младших 8

Блин, точно, хороший способ) Да только проблема в том что мне нужно одно число в одной итерации цикла.

https://stackoverflow.com/questions/1640258/need-a-fast-random-generator-for-c

И аще, STFW

По теме Fast Random ссылок предостаточно.

Хреновые там советы: куду никто не вспомнил, а все остальное — говно тормозное.

Странный он у тебя. У меня он молчит, как вроде и должен

Ты его подготовь сначала: выкрути в alsamixer все "усилители" громкости на максимум.

Да только проблема в том что мне нужно одно число в одной итерации цикла

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

как то так:

int genByte() {
    static int idx = 4;
    static uint32 state = 0;
    if (idx == 4) {
        idx = 0;
        state = genInt32();
    }
    idx++;
    int ret = state & 0xff;
    state >> 8;
    return ret;
}

это скорее псевдокод, чем C.

Ох, прошу прощения. Правда он медленно идет. Сомневаюсь, что кроме ioctl'я, устанавливающего sample rate, это можно исправить

Нравится?

Совсем упоротый? У /dev/dsp сильно ограничена скорость потока чтобы этот метод вообще можно было назвать «быстрым»

И значения почти одинаковы даже на максимуме

Это медленно из-за того, что по умолчанию что-то типа 8кГц + буферизация stdin/stdout. На более-менее современной звуковушке получим 2 канала на 196кГц == 392кБ/с.

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

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

его еще обрабатывать придется чтобы получить равномерное распределение.

А вообще, для задач ТСа достаточно заранее штук 16 шаблонов 8х8 пикселей нагенерировать, а потом заполнять ими изображение в случайном порядке шаблонов (а возможно — еще и с весами).

Для изображений нужна гауссиана, там равномерное нафиг не сплющилось!

Держи

#define POOL_SIZE (1024 * 64)

int pool[POOL_SIZE];
unsigned pool_position1 = 0;
unsigned pool_position2 = 0;

void init_pool(void)
{
    int i = 0;
    for (; i < POOL_SIZE; i++)
    {
        pool[i] = rand();
    }
}

int fast_rand(void)
{
    return pool[(pool_position1++) % POOL_SIZE] + pool[(pool_position2 += 37) % POOL_SIZE];
}

На моей машине обгоняет библиотечный rand() раз в десять.

чем этот велосипед лучше метода фибоначчи?

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

Времена ZX-Spectrum прошли, какие могут быть таблицы для синуса? Вам хочется радости от cache miss?

К примеру - вычислять синус угла с помощью sin или корень с помощью sqrt. Как можно больше данных подготавливай до игрового цикла (в случае синуса - заранее созданная таблица угол -> значение).

Как там в 80-х?

Сейчас нужно все «синусы» (если это становится узким местом, что маловероятно) в шейдеры переносить, где им и место. И без всяких таблиц.

P.S. Кстати если у ТС нормальный OpenGL а не тупой растр из 90-х (привет, SDL) можно подумать насчет шейдеров (упомянутая Эдиком куда - по-сути, тоже самое).

andreyu, Kosyak

Ну а потом мы жалуемся, что крузисы хотят i7&32gb. Конечно, давайте положим хер на рефакторинг тоже и на тесты и на старые компы и на всё положим, просто заявим минимальную конфигурацию какую удобно, будем писать говнокод и хихикать.

крузис на 6600 шел с 512 мб ОЗУ.

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

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

http://xkcd.com/221/

У Кнута много генераторов.

и на всё положим

И на конституцию!?!?!?
:)

Конечно, давайте положим хер на рефакторинг тоже и на тесты

Лихо ты перескочил.

старые компы

Это ты про спектрум? Думаю на него можно положить.

Ну а потом мы жалуемся, что крузисы хотят i7&32gb

Look-up table требует доп. память, так к слову. Ну и, как заметил andreyu, на современных процессорах (начиная с Pentium Pro) этот вариант будет ещё и тормознее чем просто вычисление синуса.

писать говнокод

Ты что, уже определил, что узкое место в твоей проге - рандом? И что тебе его действительно нужно запускать столько раз, сколько ты это делаешь?

Положить на тесты тут хочешь ты. Преждевременная оптимизация (и соотв. без проверки) - бред и зло.

Шум на изображении можно один раз сгенерировать, а затем юзать без изменений. Или крутить на 90 градусов.

Я за вариант с таблицей - потрать несколько мегабайт под такую таблицу - проблема что ли? Ничего не потеряешь, что может быть быстрее?

Вы что, какие таблицы?

Регистр сдвига с обратной связью: http://en.m.wikipedia.org/wiki/Linear_feedback_shift_register

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

Гугл: адитивно-мультипликативный метод. Простая арифметика, на OpenCL или куда легко запилить, я думаю.

template<int a, int b, int c>
int get_random() {
    static int seed = 7;
    seed = (seed * a + b) % c;
    return seed;
}

int main() {
    int pseudoRandom = get_random<23, 51, 203>();
}

a, b и c лучше всего выбирать взаимно-простыми. c — максимальное значение. На википедиях наверняка найдутся более удачные комбинации a, b и c чем у меня в примере

Еще раз, выборка из таблицы будет дольше и накладнее, чем расчет синуса в рилтайме. Я вам про кеш-мисс не зря написал.

a, b и c лучше всего выбирать взаимно-простыми. c — максимальное значение. На википедиях наверняка найдутся более удачные комбинации a, b и c чем у меня в примере

Я делаю так:

unsigned m_seed;

unsigned getRandom(unsigned min, unsigned max)
{
    m_seed = 214013 * m_seed + 2531011;

    return min + (m_seed ^ m_seed >> 15) % (max - min + 1);
}

Откуда взял эти значения не помню, этот код у меня уже лет 10 не менялся.