srand - принцип работы или как написать свой srand

[SiMM]

> И использование C в проекте не возможно по ряду серьезных причин.
При чём тут C или PHP, когда тебя интересует АЛГОРИТМ?

 

[Crazy]

SiMM, ну что ты сбиваешь мальчика с мысли -- он же на ходу отмазки придумывает.

 

[Фанат]

я бы сказал - "зачем кайф ломаешь" =)
мальчик так собой гордился, придумав такой ловкий ход =)

 

[SeY]

Господа, извиняюсь, был в отъезде.

Итак

> При чём тут C или PHP, когда тебя интересует АЛГОРИТМ?
Товарищ уточнил относительно С, я ответил.

2 Фанат , Crazy - рад, что вам понравилось

 

[netdog]

Причем в целях экономии ресурсов нельзя пользоваться массивами, переменными и т.п.. Т.е. первую область сохранить нельзя.

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

А где-же ты в пхп всё это хранить собираелся(шся)?

Ну вы же не знаете всей сути проекта. Это - только малая часть, подзадача. И использование C в проекте не возможно по ряду серьезных причин. Одна из основных - заказчик проекта в корне против С, по причинам, которые известны только ему =)

ты считаешь что ты сможешь на писать на _php_ лучший алгоритм чем он реализован в пыхе? как бы ты не изгибался, лучше не напишешь и тем более быстрее.
Алгоритм это конечно интересно, но даже если кто-то и писал врядли это сможет вспомнить, алгоритмы понимаешь такие вещи, написал, через месяц забыл.
А гугл для тебя самый лучший вариант. Ну и если очень-очень захотелось, лезешь в исходники пхп и ищешь то что тебе надо, в полном комплекте, не морочя людям голову показывая свои выпирдосы. ;-)

 

[SeY]

Мне не надо было лучше, мне надо было так же, но не много по другому. Но вопрос в общем решен давно.

 

[Demiurg]

какие мы таинственные ...

 

[Crazy]

Demiurg, это не таинственность. Просто ребенок устал врать. Да и фантазия истощилась...

 

[valyala]

Подскажите плиз, может кто сталкивался. Есть задача : надо сгенерить одну случайную область чисел, а потом на основе ее сгенерить вторую. Первая должна содержать вторую. Причем в целях экономии ресурсов нельзя пользоваться массивами, переменными и т.п.. Т.е. первую область сохранить нельзя.

Для начала проведем небольшой ликбез.

Не существует алгоритмов, способных генерировать последовательность случайных чисел (СЧ), т.к. любой алгоритм детерминирован по определению.

Любой алгоритмический генератор "случайных" (на самом деле псевдослучайных) чисел (ГСЧ) можно представить в виде детерминированного конечного автомата (ДКА). Это означает, что значение очередного "случайного" числа является функцией от текущего состояния ДКА и его входных параметров. Обычно в данных генераторах входные параметры не используются.

Из вышесказанного следует, что любая последовательность, полученная с помощью алгоритмического генератора СЧ, является периодической, т.к. любой ДКА обладает конечным набором состояний.

Плавно переходим от лирики к физике.
Функция [m]srand[/m] не генерирует псевдослучайную последовательность. Она всего лишь устанавливает начальное состояние ДКА. Функция [m]rand[/m] переводит ДКА в следующиее состояние и возвращает его выходное значение.

А теперь, собственно, ответ на поставленный вопрос.
Любой алгоритмический ГСЧ можно представить не только в виде ДКА, но и функции, зависящей от двух параметров - начального вектора инициализации IV (начальное состояние ДКА) и порядкового номера N числа в последовательности. Тогда очевидно решение поставленной задачи:
- "случайность" последовательности задается с помощью IV. Для его генерации можно использовать, например, функцию [m]microtime[/m].
- первая последовательность генерируется в цикле

for (i=0; i<N1; i++) rnd_num = f(IV, i);

где N1 - количество чисел, которые нужно сгенерировать в первой последовательности;
f() - функция ГСЧ;
- вторая последовательность генерируется в цикле

for (i=0; i<N2; i++) rnd_num = f(IV, rand() % N1);

где N2 - количество чисел, которые нужно сгенерировать во второй последовательности. Очевидно, что все числа из второй последовательности будут принадлежать первой последовательности. И не нужно использовать никаких массивов для хранения первой последовательности.
Главная проблема - создать функцию ГСЧ f(). В задачах, где безопасность не является критическим фактором, можно воспользоваться любой хэш-функцией в качестве f(). Например, функцией [m]crc32[/m], которая вычисляется весьма быстро:

function f($iv, $n)
{
    return crc32($iv . $n);
}

Функцией [m]crc32[/m] не рекомендуется пользоваться в приложениях, где важна безопасность, т.к. при ее использовании сравнительно легко найти корреляцию между выходом данной функции и значением $n при неизвестном $iv, либо даже вычислить $iv по набору выходных значений. В этом случае лучше заменить [m]crc32[/m] на криптографически стойкую хэш-функцию. Например, на [m]md5[/m] или [m]sha1[/m]. Но в этом случае резко падает производительность ГСЧ, т.к. данные функции спроектированы таким образом, чтобы тратить сравнительно большое количество тактов процессора на их вычисление (в сотни тысяч раз больше, нежели для [m]crc32[/m]). Это необходимо для уменьшения вероятности успешной brute-force атаки на хэши, полученные с помощью данных функций.

 

[Crazy]

valyala, да ты садист... Уважаю.