Вот реализация Random(int) в Delphi 6:

считаем что символ PIC НЕопределен, на сколько я понял это под Kylix (GOT - global offset table, вроде это понятие из области unix-подобных систем)

{$IFDEF PIC}
function GetGOT: LongWord; export;
begin
asm
MOV Result,EBX
end;
end;
{$ENDIF}

procedure _RandInt;
asm
{ ->EAX Range }
{ <-EAX Result }
PUSH EBX
{$IFDEF PIC}
PUSH EAX
CALL GetGOT
MOV EBX,EAX
POP EAX
MOV ECX,[EBX].OFFSET RandSeed
IMUL EDX,[ECX],08088405H
INC EDX
MOV [ECX],EDX
{$ELSE}
// обнуляем EBX, зачем , можно просто IMUL EDX,[RandSeed],08088405H
XOR EBX, EBX
// перемножаем RandSeed и 134775813 (08088405H)
IMUL EDX,[EBX].RandSeed,08088405H
// увеличиваем на еденицу старшее двойное слово результата умножения
INC EDX
// сохраняем старшее двойное слово результата умножения как новый RandSeed
MOV [EBX].RandSeed,EDX
{$ENDIF}
// умножаем преданный в качестве параметра диапазон на старшее двойное слово предыдущего результата
MUL EDX
// берем старшее двойное слово от предыдущего умножения, это и будет результат
MOV EAX,EDX
POP EBX
end;

знающие люди напишите формулу чему равно a, b, m если это x(n+1)=a*x(n)+b mod m , или это что-то другое?
у мя не выходит, не дружен я с математикой

Цитата

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

часто в качестве m берут что-то вроде 2^32
по-моему, это совсем неплохо для периода

Цитата

// перемножаем RandSeed и 134775813 (08088405H) // увеличиваем на еденицу старшее двойное слово результата умножения // сохраняем старшее двойное слово результата умножения как новый RandSeed

это был бы в точности тот алгоритм, который и предполагается, если последние две операции выполнялись не над старшим dword, а над младшим.
в этом случае a=134775813, b=1, m=2^32
если все же операции выполнять над старшим словом, может получиться такая наприятная ситуация:
пусть RandSeed=1 (должно же такое бывать)
тогда 134775813*RandSeed=134775813
старшее dword результата произведения равно 0
тогда RandSeed=1
к сожалению, я не знаю этого ассемблера и ориентируюсь только по комментариям...

хм, я не много ошибся в разборе поцедуры. После первого умножения идет работа с младшим двойным словом. Вот верный вариант:

procedure _RandInt;
asm
{ ->EAX Range }
{ <-EAX Result }
PUSH EBX
{$IFDEF PIC}
PUSH EAX
CALL GetGOT
MOV EBX,EAX
POP EAX
MOV ECX,[EBX].OFFSET RandSeed
IMUL EDX,[ECX],08088405H
INC EDX
MOV [ECX],EDX
{$ELSE}
// обнуляем EBX, зачем , можно просто IMUL EDX,[RandSeed],08088405H
XOR EBX, EBX
// перемножаем RandSeed и 134775813 (08088405H)
IMUL EDX,[EBX].RandSeed,08088405H
// увеличиваем на еденицу младшее двойное слово результата умножения
INC EDX
// сохраняем младшее двойное слово результата умножения как новый RandSeed
MOV [EBX].RandSeed,EDX
{$ENDIF}
// умножаем преданный в качестве параметра диапазон на младшее двойное слово предыдущего результата
MUL EDX
// берем старшее двойное слово от предыдущего умножения, это и будет результат
MOV EAX,EDX
POP EBX
end;

Это сообщение отредактировал(а) cully - 22.3.2003, 03:45

и еще вопрос в догонку: чем обоснован выбор a=134775813?

От этого числа (в большей степени, чем от b) зависит равномерность распределения выходных значений. Если немного попреобразовывать эту формулу, можно прийти к линейному регистру сдвига:

x(n)=a*x(n-1)+b
x(n+1)=a*x(n)+b
b=x(n)-a*x(n-1)
x(n+1)=a*x(n)+x(n)-a*x(n-1)
-----------------------------------
x(n+1)=(a+1)*x(n)-a*x(n-1) [надеюсь я ничего не напутал ]
(только теперь надо задавать два начальных значения)

Линейные регистры сдвига довольно хорошо изучены. Известны зависимости некоторых показателей качества генерируемых ними последовательностей от коэффициентов линейного рагистра. Нам в институте дали только способ определения периода с помощью характеристических полиномов регистра, а показателей качества псевдослучайных последовательностей дали около десятка.
Думаю, обоснование выбора подобных чисел можно найти в книгах по криптологии или связанным с ней дисциплинам...
P.S.
А первое, что приходит в голову - a не должно быть делителем m (в нашем случае оно просто должно быть нечетным), но это - лишь первый шаг для сужения области поиска подходящих чисел

ок, все понятно, но вернемся к вопросу топика

есть у меня большая выборка значений (100 000) и что делать дальше? как построить гипотезу о вожмоном устройстве датчика? ... и предсказать следуещее 100 001 значение ?

Это сообщение отредактировал(а) cully - 23.3.2003, 10:34

наконец-то проделал несколько экспериментов
вот некоторые результаты:

У генератора x(n+1)=a*x(n)+b есть неприятная особенность: на каждом шаге меняется четность.
(это если "a" нечетное, иначе четность вообще меняться не будет)

Цитата

И в BC3.1, и в TP7.0, и в VC6++, и Linux (соответсвенно, в perl, си, си++ под линух).

Боюсь, что это не так. В BC++3.1 и в VC++6.0 генератор случайных чисел построен по-другому (к сожалению, не знаю как)
Этот генератор я обнаружил только в Delphi (наверное, он есть и в TP7.0, но я не проверял)
В C++ генератор другой, он не обладает вышеописанным свойством

Цитата

есть у меня большая выборка значений (100 000)

Для предсказания этого генератора нужно не больше трех последовательных чисел:
1, если известны a,b
2, если известно что-то одно
3, если оба коэффициента неизвестны

А вот, собственно, алгоритм предсказания:
x(n+1)=a*x(n)+b mod m
m=2^32
a=134775813
b=1

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

Цитата

как построить гипотезу о вожмоном устройстве датчика

Скорее всего, нужно перебирать все известные гипотезы, пока одна не подойдет.

Состояние рассмотренного генератора полностью описывается его выходом (RandSeed)
Состояние любого реккурентного регистра полностью описывается несколькими последними выходами
Но ведь можно построить генератор, состояние которого будет скрыто, а за выход будет браться какая-то функция от состояния
такой генератор значительно сложнее взломать.
А еще достаточно добавить подходящую нелинейность, чтобы практически обезвредить весь линейный анализ.

Цитата

главное что бы данных было достаточно, а именно больше периода повторения

Конечно, если есть все данные за период, можно с легкостью предсказать каждое следующее значение. Однако, почти всегда период измеряется величинами порядка 2^32.

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

P.S.
извините за большой размер сообщения, оно все как-то само получилось

2maxim1000:Угу, именно этот способ я и имел в виду в начале дискуссии.

Цитата

Скорее всего, нужно перебирать все известные гипотезы, пока одна не подойдет.

По-моему здесь имелся в виду статистический анализ.

Цитата

QUOTE  И в BC3.1, и в TP7.0, и в VC6++, и Linux (соответсвенно, в perl, си, си++ под линух). Боюсь, что это не так. В BC++3.1 и в VC++6.0 генератор случайных чисел построен по-другому (к сожалению, не знаю как)

srand от VC6++:

Цитата

004027A0 55                  push        ebp 004027A1 8B EC                mov        ebp,esp 004027A3 8B 45 08            mov        eax,dword ptr [seed] 004027A6 A3 50 3A 42 00      mov        [holdrand (00423a50)],eax 004027AB 5D                  pop        ebp 004027AC C3                  ret

rand() от VC6++:

Цитата

004027B0 55                  push        ebp 004027B1 8B EC              mov        ebp,esp 004027B3 A1 50 3A 42 00      mov        eax,[holdrand (00423a50)] 004027B8 69 C0 FD 43 03 00  imul        eax,eax,343FDh 004027BE 05 C3 9E 26 00      add        eax,269EC3h 004027C3 A3 50 3A 42 00      mov        [holdrand (00423a50)],eax 004027C8 A1 50 3A 42 00      mov        eax,[holdrand (00423a50)] 004027CD C1 F8 10                sar        eax,10h 004027D0 25 FF 7F 00 00      and        eax,7FFFh 004027D5 5D                  pop        ebp 004027D6 C3                  ret

Другими словами, в VC6++ алгоритм у rand() такой:

seed' = ( seed * 0x343FD (знаковое умножение) + 0x269EC3 ) mod 2^32;

результат от ф-ции rand будет:

rand() = (seed' >> 16) & 7FFFh;

Если не веришь, задай конкретные значения в srand'е (0,1 ...) и проверь ;)

Тут пришел Chingachguk и все опошлил

Цитата

rand() = (seed' >> 16) & 7FFFh;

шутка?

Kstati, pro integral - ja ego privel k vidu gamma funkcii i poluchilos', chto ot 0 do +infinity budet 2 (=2*г(1)=2*0!=2)

Цитата

шутка?

Почему ?

mov eax,[holdrand (00423a50)] // eax = seed'
sar eax,10h // eax >> = 16
and eax,7FFFh // eax & = 0x7FFFh

Так что безо всяких шуток. И в BC3.1 то же самое. Проверь так:

max=0;
for (i=0;i<10000;i++)
{
randval= rand();
if max<randval max=randval;
}
printf("MaxRand=%u",randval);

А вот в linux совсем иначе: чаще всего процедуры типа drand/srand компилируются с дефайном MAX_BITS 48.

Цитата

Kstati, pro integral

Так то ж ... аналитически. И зачем gamma, если такая простая подинтегральная (exp(-const*t)) ?

Это сообщение отредактировал(а) Chingachguk - 24.3.2003, 22:28

Кстати, а какие способы оценки качества псевдослучайных последовательностей существуют?

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

Например, автокорреляционная функция:

Цитата

long AKF(byte *Data,int Size,int StartBytePos,int StartBytesSize) {   int  i,j;   int  Tay;   byte b;   int  bNorm[8*100];   int  f;   long Maxf=0;   int  SizeInBits=Size*8;   for (i=0;i<Size;i++)   {     b=Data[i];     for (j=0;j<8;j++)     {       if ((b&0x80)==0x80)         bNorm[i*8+j]=1;       else         bNorm[i*8+j]=-1;       b<<=1;     }   }   //bSum=0;   //for (i=0;i<Size*8;i++) bSum+=(bNorm[i])*(bNorm[i]);   for (Tay=StartBytePos*8;Tay<((StartBytePos+StartBytesSize)*8);Tay++)   {     f=0;     for (i=0;i<Size*8;i++) f+=(bNorm[i])*(bNorm[(i+Tay)%(SizeInBits)]);     if (f<0) f=-f;     Maxf+=f;   }   return(Maxf); }

Но это специфическая реализация (моя) для конкретного дела, так что лучше смотреть sources ;)

а как быть с "Алгоритм Л'Экюера, комбинирующий две последовательности" ?

http://algolist.manual.ru/maths/generator/lequer.php