Генератор случайных чисел: какой использует Delphi?

← →
Ega23 © (2008-03-24 13:31) [0]

какой-то свой или системный? Интересует описание алгоритма (если алгоритм открыт), а также вероятностные выкладки по повторяющимся значениям (например, через какое время произойдёт появление одинаковых значений с точки зрения вероятности при вызове Random, например, раз в 20 миллисекунд).

← →
Игорь Шевченко © (2008-03-24 13:32) [1]

Чего ты такое творишь ?

← →
Рамиль © (2008-03-24 13:34) [2]

Похоже свой генератор GUID :)

← →
31512 (2008-03-24 13:41) [3]

Он пишет матрицу...

← →
Reindeer Moss Eater © (2008-03-24 13:41) [4]

MS CryptoAPI 2.0

CryptGenRandom

← →
Ega23 © (2008-03-24 13:47) [5]

> Похоже свой генератор GUID :)

фактически да. Стандартный GUID всё-таки не устраивает...

> Чего ты такое творишь ?

Нужно уметь генерировать уникальное значение на событие в распределённой системе. Событий много. Каждый из распределённых "блоков" имеет свой уникальный идентификатор (по размеру - не более word, возможно не 16 бит, а поменьше, это пока под вопросом). На каждом "блоке" возможно наличие нескольких потоков, обрабатывающих события. Каждый поток должен уметь генерировать вот такие события.
UID должен гарантировано давать уникальное значение раз в микросекунду (это нижний предел).
Вероятность повторения UID - не ранее, чем через 50 лет.
Также должна быть защита уникальности при ручном переводе системного времени.
Желательно запихнуть это дело в возможно меньшее число байт.

Вот такая вводная.

Пока думается что-то, типа сочетания: ID блока, Handle потока, значение QuweryPerfomanceCounter (возможно, всего 7 байт вместо 8) + что-то ещё.
Вот думаю в это "что-то ещё" Random-значение класть.

← →
tesseract © (2008-03-24 14:02) [6]

> Интересует описание алгоритма (если алгоритм открыт),

У Джулина Бакнела, есть полное его описание. Алгоритм свой, распределение значений равномерное.

← →
DVM © (2008-03-24 14:10) [7]

> Ega23 © (24.03.08 13:47) [5]

что бы ты там не наизобретал, если это что-то НЕ БУДЕТ использовать в процессе генерации какой-то аппаратно предопределенной ГЛОБАЛЬНО УНИКАЛЬНОЙ величины, то уникальности 100% не достичь.

← →
DVM © (2008-03-24 14:12) [8]

Да будь вероятность совпадения хоть 10 в минус 100 степени, никто и никогда не сможет поручиться, что это совпадение не будет получено при первом же испытании. Если это еще и повлечет за собой необратимые последствия, то становится стремно как то.

← →
Игорь Шевченко © (2008-03-24 14:23) [9]

> Handle потока

а если завтра запустится поток с таким же Handle ?

← →
MBo © (2008-03-24 14:24) [10]

>какой-то свой или системный?
свой, в system,pas

>Интересует описание алгоритма (если алгоритм открыт),
линейный конгруэнтный генератор

>через какое время произойдёт появление одинаковых значений
Если генерируется Random(MaxInt)+1, то будет 2^31 неповторяющихся значений

Улучшенные алгоритмы - у Бакнелла в книге, как уже сказали, также можно посмотреть статьи Marsaglia, Mersenne Twister

← →
Jeer © (2008-03-24 14:41) [11]

Надеюсь, 2^144 хватит.

unit rmar;
{
This random number generator originally appeared in "Toward a Universal
Random Number Generator" by George Marsaglia and Arif Zaman.
Florida State University Report: FSU-SCRI-87-50 (1987)

It was later modified by F. James and published in "A Review of Pseudo-
random Number Generators"

THIS IS THE BEST KNOWN RANDOM NUMBER GENERATOR AVAILABLE.
(However, a newly discovered technique can yield
a period of 10^600. But that is still in the development stage.)

It passes ALL of the tests for random number generators and has a period
of 2^144, is completely portable (gives bit identical results on all
machines with at least 24-bit mantissas in the floating point
representation).

The algorithm is a combination of a Fibonacci sequence (with lags of 97
and 33, and operation "subtraction plus one, modulo one") and an
"arithmetic sequence" (using subtraction).
========================================================================
C language version was written by Jim Butler, and was based on a
FORTRAN program posted by David LaSalle of Florida State University.

Adapted for Delphi by Anton Zhuchkov (fireton@mail.ru) in February, 2002
}

interface

{ This is the initialization routine for the random number generator RANMAR()
NOTE: The seed variables can have values between: 0 <= IJ <= 31328
0 <= KL <= 30081
The random number sequences created by these two seeds are of sufficient
length to complete an entire calculation with. For example, if sveral
different groups are working on different parts of the same calculation,
each group could be assigned its own IJ seed. This would leave each group
with 30000 choices for the second seed. That is to say, this random
number generator can create 900 million different subsequences -- with
each subsequence having a length of approximately 10^30.

Use IJ = 1802 & KL = 9373 to test the random number generator. The
subroutine RANMAR should be used to generate 20000 random numbers.
Then display the next six random numbers generated multiplied by 4096*4096
If the random number generator is working properly, the random numbers
should be:
6533892.0 14220222.0 7275067.0
6172232.0 8354498.0 10633180.0
}
procedure RMSeed(IJ, KL : Integer);

{ This is the random number generator proposed by George Marsaglia in
Florida State University Report: FSU-SCRI-87-50
}
function RMRandom: Double;

const
Seeded : Boolean = False;

implementation
uses SysUtils;

var
u : array [0..97] of Double;
c, cd, cm : Double;
i97, j97 : Integer;

procedure RMSeed(IJ, KL : Integer);
var
i, j, k, l, ii, jj, m : Integer;
s, t : Double;
begin
if (ij<0) or (ij>31328) or (kl<0) or (kl>30081) then
raise Exception.Create("Random generator seed not within the valid range!");

i := (ij div 177) mod 177 + 2;
j := ij mod 177 + 2;
k := (kl div 169) mod 178 + 1;
l := kl mod 169;

for ii:=1 to 97 do
begin
s := 0.0;
t := 0.5;
for jj:=1 to 24 do
begin
m := (((i*j) mod 179)*k) mod 179;
i := j;
j := k;
k := m;
l := (53*l + 1) mod 169;
if ((l*m) mod 64 >= 32) then s := s + t;
t := t*0.5;
end;
u[ii] := s;
end;

c := 362436.0 / 16777216.0;
cd := 7654321.0 / 16777216.0;
cm := 16777213.0 / 16777216.0;

i97 := 97;
j97 := 33;

Seeded := True;
end;

function RMRandom: Double;
var
uni: Double;
begin
if not Seeded then
raise Exception.Create("Random generator not seeded!");
uni := u[i97] - u[j97];
if (uni < 0.0) then uni := uni + 1.0;
u[i97] := uni;
Dec(i97);
if i97 = 0 then i97 := 97;
dec(j97);
if j97 = 0 then j97 := 97;
c := c - cd;
if c < 0.0 then c := c + cm;
uni := uni - c;
if uni < 0.0 then uni := uni + 1.0;
Result := uni;
end;

end.

← →
Jeer © (2008-03-24 14:46) [12]

Для изучения состояния дел можно заглянуть сюда:
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

← →
Ega23 © (2008-03-24 15:01) [13]

> а если завтра запустится поток с таким же Handle ?

Кстати. А можно ли как-нибудь узнать количество запусков Windows с момента установки?

← →
Reindeer Moss Eater © (2008-03-24 15:03) [14]

о майн гот :)

← →
Ega23 © (2008-03-24 15:05) [15]

> Reindeer Moss Eater © (24.03.08 15:03) [14]
>
> о майн гот :)

Не упоминай Имя Господа всуе! :)

← →
Рамиль © (2008-03-24 17:53) [16]

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

← →
@!!ex © (2008-03-24 19:27) [17]

Эммм. Объясните мне, плиз, как рандом влияет на уникальность?
Применение, хоть миллион битного рандома не даст гарантию, что УИД не повторится, оно лишь уменьшит эту вероятность. Собственно как и все остальные параметры.

Как уже было сказано, делается железка, стоимостью в 5$, тыкается в USB, к ней пишется драйвер.
Все, что умеет железка - отдавать свой номер. Скажем 12 байтное число. И все.
Налаживаем выпуск этой железки, и в каждую суем уникальный номер. Задача решена.
На программном уровне эта задача НЕ РАЗРЕШИМА.

← →
kovrigin the permutator (2008-03-24 19:32) [18]

@!!ex © (24.03.08 19:27) [17]

А как же тепловой шум?

← →
@!!ex © (2008-03-24 19:39) [19]

> тепловой шум?

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

← →
Anatoly Podgoretsky © (2008-03-24 21:23) [20]

> Игорь Шевченко (24.03.2008 14:23:09) [9]

А если будет перезапуск, то и PerformanceCounter насчет с нуля.
Блок фиксированое, Handle может повторяться, а PerformanceCounter тем более, так что это не те точки для генератора. Да и на дату нельзя опереться по словам автора. Разве что постоянно записывать последнее значение на диск и потом складывать сохраненое с текущим.

← →
Anatoly Podgoretsky © (2008-03-24 21:24) [21]

> Ega23 (24.03.2008 15:01:13) [13]

Можно если при запуске увеличивать счетчик на энергонезавимом устройстве хранения при каждом запуске.

← →
{RASkov} © (2008-03-24 21:53) [22]

> Можно если при запуске увеличивать счетчик на энергонезавимом
> устройстве хранения при каждом запуске.

Винда же это вроде где-то хранит уже.... или откуда берет данные, такие как "Число входов в систему" - Everest ?

← →
Ega23 © (2008-03-24 22:07) [23]

> Пусть числа генерит ОДИН сервер в расп. системе.

Я такое уже предлагал. По ряду причин (вполне объективных) отвергнуто.

← →
Ega23 © (2008-03-24 22:08) [24]

Вобщем я тут сегодня с Розычем пообщался, он предлагает составной ключ: GUID + значение QueryPerformanceCounter

← →
DVM © (2008-03-24 22:13) [25]

> он предлагает составной ключ: GUID + значение QueryPerformanceCounter

Приплюсуйте туда еще температуру процессора и MD5 от имени того, кто убил Кенни. ВСЕ РАВНО СОВПАСТЬ МОЖЕТ!

← →
Ega23 © (2008-03-24 22:22) [26]

> ВСЕ РАВНО СОВПАСТЬ МОЖЕТ!

Может, кто спорит-то? То, что гарантировано-уникальное значение сгенерировать не удастся - это и ежу понятно. Вопрос в уменьшении вероятности при разумном размере ключа

← →
DVM © (2008-03-24 22:24) [27]

> Ega23 © (24.03.08 22:22) [26]

А какие последствия может иметь такое совпадение в твоем случае?

← →
ferr (2008-03-24 22:50) [28]

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

Это возможный выход, за незнанием проблемы, говорю и про него..

P.S. для тех кто решил докапаться, целое число это не int, a byte[].

P.S.S. А автору лучше пойти и почитать, если простенько то в бакнеле об этом глава, если сложненько, то кнут 2ой том.

> А какие последствия может иметь такое совпадение в твоем
> случае?

Ну не фатальные, но - неприятные.

> DVM © (24.03.08 14:10) [7]
> если это что-то НЕ БУДЕТ использовать в процессе генерации
> какой-то аппаратно предопределенной ГЛОБАЛЬНО УНИКАЛЬНОЙ
> величины
А почему, собственно, аппаратной? Почему не административной? В бытность, тупо распределяли диапазоны генераторов по объектам и имели ту самую уникальнось при слиянии. Не хватает 32 -х бит (а с таким max темпом - точно не хватит), добавьте разрядности. В сухом остатке, имеем на месте простой алгоритм (inc/gen_id). И составной ключ (номер хоста, номер процесса (уж это на одном хосте не проблема), просто, ключ) будет уникален. Куда все это впихнуть - зависит от количества хостов и процессов на каждом из них. Прошу извинения за некоторую несвязность, но если на одном хосте можно обеспечить уникальность, то почему не добавить в ключ уникальную информацию об участке, филиале и т.п.? Так сказать, включить не программистский, а административный ресурс ("Я сказал, что ваши ID будут начинаться с 2000000000" и заканчиваться на 2999999999, потому, что ваш номер - 2). Всё сказал. Пинайте. Да, то, что 2999999999 в 32 бита не влазит, я в курсе :)

> 2999999999 в 32 бита не влазит
Со знАком, естественно...

У тебя 2^16 воможных значений. И какие-то там десятки раз в секунду это генерируется. В году 31536000, пусть 315360000 генераций, то есть за 50 лет на одной машине переберем 15768000000, то есть 2^34. Это намного превышает количество возможных значений. Так что 50 лет - нереальная цифра. Увеличивай длину ключа.

> Ega23 © (24.03.08 22:07) [23]
>
> > Пусть числа генерит ОДИН сервер в расп. системе.
>
>
> Я такое уже предлагал. По ряду причин (вполне объективных)
> отвергнуто.

Ну, тогда пусть кто-то выдает уникальный марекер один раз, при инсталляции сервиса, один раз-то уж запросить можно. Можно даже в момент регистрации выдавать вам самим (если оная предусмотрена). Потом сцеплять его с генерируемым.

> Ну, тогда пусть кто-то выдает уникальный марекер один раз,
> при инсталляции сервиса, один раз-то уж запросить можно.
> Можно даже в момент регистрации выдавать вам самим (если
> оная предусмотрена). Потом сцеплять его с генерируемым.

Это-то есть. Только толку? Представь, что сервис у тебя рухнул. Каким образом он запомнит последнее выданное ID?

> Только толку? Представь, что сервис у тебя рухнул. Каким
> образом он запомнит последнее выданное ID?

Рухнул - переинсталлировать, выдать новый маркер. Из бэкапа восстанавливать только данные.

> Рамиль © (25.03.08 09:54) [36]

Поверь, все эти варианты уже были перебраны, предложены и отвергнуты по вполне разумным причинам.
Убеждать меня в том, что то, что ты предлагаешь - самое лучшее решение, не нужно. Во-первых, мне это и самому в первый момент в голову пришло, а во-вторых - причины отвержения действительно разумны.

> и MD5 от имени того, кто убил Кенни.

Кстати, а кто его убил?

> Кстати, а кто его убил?

Они надели волшебную шляпу на Снеговика, он ожил и убил Кенни.

Ну как хочешь, хозяин - барин:)

> Кстати, а кто его убил?

Ты че не знал? Его убили сволочи.

> Это-то есть. Только толку? Представь, что сервис у тебя
> рухнул. Каким образом он запомнит последнее выданное ID?

Запоминать каждый раз при генерации? Сгенерил-Запомнил-Отдал.

Генератор случайных чисел: какой использует Delphi? Найти похожие ветки