Неверов Евгений Викторович
Меню сайта
Категории раздела
Программирование на языке Паскаль [27]
В данной категории представлены новые функции, созданные на языке Паскаль, которые могут пригодиться при написании своих программ
Программирование на Delphi [18]
В данной категории представлены полезные подпрограммы, которые могут пригодиться при написании своих программ, а также рассматриваются примеры готовых проектов, создаваемых в среде программирования Delphi
Программирование на HTML [0]
В данной категории рассматриваются примеры готовых проектов, создаваемых на языке HTML
Прочее [0]
Свободная тематика
Мини-чат
200
Наш опрос
Чем Вы занимаетесь?
Всего ответов: 36
Статистика

Рейтинг@Mail.ru
Онлайн всего: 1
Гостей: 1
Пользователей: 0
Форма входа
Главная » Статьи » Программирование на Delphi [ Добавить статью ]

Генератор псевдослучайных чисел (ГПСЧ). Часть 1

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


1. Как работает процедура Randomize?


Процедура Randomize инициализирует генератор случайных чисел, задавая значение переменной RandSeed, вычисленное с помощью системных часов. Переменная RandSeed - это глобальная предопределенная переменная, объявленная в модуле System. Она задает начальное значение для генератора случайных чисел. Переменная RandSeed также устанавливает генератор случайного числа на следующее значение.


procedure Randomize1;
var SystemTime: TSystemTime;
begin
   GetSystemTime(SystemTime);
   With SystemTime do
      RandSeed:=((wHour*60 + wMinute)*60 + wSecond)*1000 + wMilliseconds;
end;

В данной процедуре видно, что переменная RandSeed зависит от системных часов (время всемирное - по Гринвичу). При запуске программы эта переменная равна нулю. Поэтому при запуске программы надо хотя бы один раз вызвать процедуру Randomize, которая устанавливает начальное значение переменной RandSeed из данных системного времени.

Так как программа запускается в какое-то случайное время, то и значение переменной RandSeed будет случайным. А, следовательно, и функция Random будет возвращать случайные значения.

Исходя из того, что процедура Randomize задает начальное значение переменной RandSeed на основе текущего времени компьютера, можно предположить, что, например, если запустить программу сегодня в 12:00:00 и завтра в это же время, то функция Random вернет одинаковые числа. К сожалению, проверить это очень трудно, так как запустить программу в одно и то же время с точностью до миллисекунды будет практически невозможно.

Например, допустим, что сейчас 10 часов, 54 минуты, 38 секунд и 812 миллисекунд. В компьютере установлен 3-й часовой пояс (UTC+03:00, Москва). В этом случае всемирное время равно 7:54:38,812. Тогда переменная RandSeed примет значение 28478812 (((7*60 + 54)*60 + 38)*1000 + 812).

Рассмотрим еще пример. Запустим 2 процедуры Randomize и Randomize1 при запуске программы, а результаты переменной RandSeed выведем в Memo1 и Memo2.


procedure TForm1.FormCreate(Sender: TObject);
begin
   Randomize;
   Memo1.Text:=IntToStr(RandSeed);
   Randomize1;
   Memo2.Text:=IntToStr(RandSeed);
end;

После запуска программы увидим, что значение переменной RandSeed в обоих случаях совпадает. Это доказывает то, что RandSeed действительно зависит от системных часов.

Примечание. В названиях процедур (или функций) будем добавлять порядковые номера (1, 2, 3, ...) для того, чтобы не переопределять системные процедуры (или функции).


2. Как работает функция Random?


Рассмотрим работу функции для целых чисел.


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


function Random1(Range: integer): integer;
var z: int64;
begin
   RandSeed:=RandSeed*$8088405 + 1;
   z:=RandSeed;
   If z<0 then
      z:=z+$100000000;
   z:=z*Range;
   Result:=z div $100000000;
end;

где

Range - диапазон случайных чисел.

Примечание. Числа, начинающие со знака "$", являются шестнадцатеричными числами.

$8088405 - 134 775 813

$100000000 - 4 294 967 296

Согласно этой функции, последовательность чисел зависит от переменной RandSeed. Но, если значение переменной RandSeed будет всегда одинаковым, то мы получим одинаковый набор случайных чисел.

Еще одна особенность заключается в том, что переменная RandSeed всегда изменяется при вызове функции Random, т.е. устанавливает генератор случайного числа на следующее значение.

Рассмотрим пример образования последовательности чисел в диапазоне от 0 до 50 (Range = 50). Процедуру Randomize вызывать не будем (RandSeed = 0). Последовательность чисел будем вызывать с помощью функций Random1 и Random (для проверки).


procedure TForm1.Button1Click(Sender: TObject);
const r = 50;
      rs = 0;
var i, a: integer;
begin
   Memo1.Clear;
   RandSeed:=rs;
   For i:=1 to 30 do
   begin
      a:=Random(r);
      Memo1.Lines.Add(Format('%d число = %d, RandSeed = %d',[i,a,RandSeed]));
   end;
   Memo2.Clear;
   RandSeed:=rs;
   For i:=1 to 30 do
   begin
      a:=Random1(r);
      Memo2.Lines.Add(Format('%d число = %d, RandSeed = %d',[i,a,RandSeed]));
   end;
end;

Тексты в Memo1 и Memo2 будут выглядеть одинаково:

1 число = 0, RandSeed = 1
2 число = 1, RandSeed = 134775814
3 число = 43, RandSeed = -596792289
4 число = 10, RandSeed = 870078620
5 число = 13, RandSeed = 1172187917
6 число = 33, RandSeed = -1410233534
7 число = 15, RandSeed = 1368768587
8 число = 8, RandSeed = 694906232
9 число = 18, RandSeed = 1598751577
10 число = 21, RandSeed = 1828254910
11 число = 4, RandSeed = 352239543
12 число = 23, RandSeed = 2039224980
13 число = 3, RandSeed = 303092965
14 число = 42, RandSeed = -683524998
15 число = 2, RandSeed = 256513635
16 число = 14, RandSeed = 1259699184
17 число = 45, RandSeed = -355259471
18 число = 18, RandSeed = 1580146294
19 число = 38, RandSeed = -967806897
20 число = 16, RandSeed = 1408429452
21 число = 34, RandSeed = -1298476099
22 число = 42, RandSeed = -669280590
23 число = 35, RandSeed = -1211254405
24 число = 15, RandSeed = 1317014376
25 число = 8, RandSeed = 698472713
26 число = 16, RandSeed = 1415176494
27 число = 23, RandSeed = 2001542631
28 число = 12, RandSeed = 1059369348
29 число = 41, RandSeed = -748714091
30 число = 13, RandSeed = 1198422506

Таким образом, при неоднократном вызове Random(50) функция выдаст последовательность чисел: 0, 1, 43, 10, 13, 33, 15, 8, 18, 21, 4, 23, 3, 42, 2, 14 и т.д.

Рассмотрим подробно образование случайных чисел. Вычисления проведем в таблице.


Число Код (команда) Значение z Значение RandSeed Значение Result Подробное вычисление
Исходные данные: Range = 50, RandSeed = 0
1 RandSeed:=RandSeed*$8088405 + 1; 0 1 0 RandSeed = RandSeed * $8088405 + 1 = 0 * 134775813 + 1 = 1
z:=RandSeed; 1 1 0 z = RandSeed = 1
If z<0 then z:=z+$100000000; < не выполняется >
z:=z*Range; 50 1 0 z = z * Range = 1 * 50 = 50
Result:=z div $100000000; 50 1 0 Result = z div $100000000 = 50 div 4294967296 = 0
Вывод: 1 число = 0, RandSeed = 1
2 RandSeed:=RandSeed*$8088405 + 1; 0 134775814 0 RandSeed = RandSeed * $8088405 + 1 = 1 * 134775813 + 1 = 134775814
z:=RandSeed; 134775814 134775814 0 z = RandSeed = 134775814
If z<0 then z:=z+$100000000; < не выполняется >
z:=z*Range; 6738790700 134775814 0 z = z * Range = 134775814 * 50 = 6738790700
Result:=z div $100000000; 6738790700 134775814 1 Result = z div $100000000 = 6738790700 div 4294967296 = 1
Вывод: 2 число = 1, RandSeed = 134775814
3 RandSeed:=RandSeed*$8088405 + 1; 0 -596792289 0 RandSeed = RandSeed * $8088405 + 1 = 134775814 * 134775813 + 1 = 18164519904586783 ($408888DC6DAC1F)
Примечание. Поскольку тип Integer принимает значения -2147483648..2147483647, занимает 4 байта, то в памяти компьютера произойдет переполнение: 18164519904586783 > 2147483647. В этом случае, в переменную RandSeed запишется только 4 младших байта ($DC6DAC1F), а остальную часть ($408888) отбросит. Т.к. число $DC6DAC1F = 3698175007 > 2147483647, в этом случае переменная RandSeed примет отрицательное значение: -596792289.
z:=RandSeed; -596792289 -596792289 0 z = RandSeed = -596792289
If z<0 then z:=z+$100000000; 3698175007 -596792289 0 If -596792289<0 then z = -596792289 + 4294967296 = 3698175007
Примечание. Размер переменной z составляет 8 байт (тип Int64), поэтому для корректной работы необходимо положительное значение, добавив небольшое условие.
z:=z*Range; 184908750350 -596792289 0 z = z * Range = 3698175007 * 50 = 184908750350
Result:=z div $100000000; 184908750350 -596792289 43 Result = z div $100000000 = 184908750350 div 4294967296 = 43
Вывод: 3 число = 43, RandSeed = -596792289
4 RandSeed:=RandSeed*$8088405 + 1; 0 870078620 0 RandSeed = RandSeed * $8088405 + 1 = -596792289 * 134775813 + 1 = <для корректной работы -596792289 заменим на 3698175007> = 3698175007 * 134775813 + 1 = 498424543184705692 ($6EAC27B33DC589C)
z:=RandSeed; 870078620 870078620 0 z = RandSeed = 870078620
If z<0 then z:=z+$100000000; < не выполняется >
z:=z*Range; 43503931000 870078620 0 z = z * Range = 870078620 * 50 = 43503931000
Result:=z div $100000000; 43503931000 870078620 10 Result = z div $100000000 = 43503931000 div 4294967296 = 10
Вывод: 4 число = 10, RandSeed = 870078620
5 RandSeed:=RandSeed*$8088405 + 1; 0 1172187917 0 RandSeed = RandSeed * $8088405 + 1 = 870078620 * 134775813 + 1 = 117265553384418061 ($1A09C6645DE2B0D)
z:=RandSeed; 1172187917 1172187917 0 z = RandSeed = 1172187917
If z<0 then z:=z+$100000000; < не выполняется >
z:=z*Range; 58609395850 1172187917 0 z = z * Range = 1172187917 * 50 = 58609395850
Result:=z div $100000000; 58609395850 1172187917 13 Result = z div $100000000 = 58609395850 div 4294967296 = 13
Вывод: 5 число = 13, RandSeed = 1172187917

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


Рассмотрим следующую функцию, написанную на ассемблере.


function Random2(Range: integer): integer;
asm
   MOV EAX,Range
   IMUL EDX,RandSeed,$8088405
   INC EDX
   MOV RandSeed,EDX
   MUL EDX
   MOV Result,EDX
end;

Комментарии:

MOV EAX,Range - присваивает регистру EAX значение Range;

IMUL EDX,RandSeed,$8088405 - умножает RandSeed на $8088405 и записывает в регистр EDX;

INC EDX - увеличивает значение регистра EDX на единицу;

MOV RandSeed,EDX - присваивает переменной RandSeed значение регистра EDX;

MUL EDX - умножает значение регистра EDX на значение регистра EAX, результат запишется в 2 регистра: EDX (старшее слово) и EAX (младшее слово);

MOV Result,EDX - присваивает переменной Result значение регистра EDX.

Рассмотрим пример образования последовательности чисел в диапазоне от 0 до 60 (Range = 60). Процедуру Randomize вызывать не будем (RandSeed = 0). Последовательность чисел будем вызывать с помощью функций Random2 и Random (для проверки).

В процедуре TForm1.Button1Click изменим постоянную r на 60, а в коде заменим функцию Random1(r) на Random2(r).

Тексты в Memo1 и Memo2 будут выглядеть одинаково:

1 число = 0, RandSeed = 1
2 число = 1, RandSeed = 134775814
3 число = 51, RandSeed = -596792289
4 число = 12, RandSeed = 870078620
5 число = 16, RandSeed = 1172187917
6 число = 40, RandSeed = -1410233534
7 число = 19, RandSeed = 1368768587
8 число = 9, RandSeed = 694906232
9 число = 22, RandSeed = 1598751577
10 число = 25, RandSeed = 1828254910
11 число = 4, RandSeed = 352239543
12 число = 28, RandSeed = 2039224980
13 число = 4, RandSeed = 303092965
14 число = 50, RandSeed = -683524998
15 число = 3, RandSeed = 256513635
16 число = 17, RandSeed = 1259699184
17 число = 55, RandSeed = -355259471
18 число = 22, RandSeed = 1580146294
19 число = 46, RandSeed = -967806897
20 число = 19, RandSeed = 1408429452
21 число = 41, RandSeed = -1298476099
22 число = 50, RandSeed = -669280590
23 число = 43, RandSeed = -1211254405
24 число = 18, RandSeed = 1317014376
25 число = 9, RandSeed = 698472713
26 число = 19, RandSeed = 1415176494
27 число = 27, RandSeed = 2001542631
28 число = 14, RandSeed = 1059369348
29 число = 49, RandSeed = -748714091
30 число = 16, RandSeed = 1198422506

Таким образом, при неоднократном вызове Random(60) функция выдаст последовательность чисел: 0, 1, 51, 12, 16, 40, 19, 9, 22, 25, 4, 28, 4, 50, 3, 17 и т.д.

Рассмотрим подробно образование случайных чисел. Вычисления проведем в таблице.


Число Код (команда) Значение регистра EAX Значение регистра EDX Значение RandSeed Значение Result Подробное вычисление
Исходные данные: Range = 60, RandSeed = 0
1 MOV EAX,Range $0000003C
(60)
0 $0
(0)
0 EAX = Range = 60 ($3C)
Примечание. В регистры будем записывать только шестнадцатеричные значения, а в скобках - десятичные.
IMUL EDX,RandSeed,$8088405 $0000003C
(60)
$00000000
(0)
$0
(0)
0 EDX = RandSeed * $8088405 = 0 * 134775813 = 0 ($0)
INC EDX $0000003C
(60)
$00000001
(1)
$0
(0)
0 EDX = EDX + 1 = 0 + 1 = 1 ($1)
MOV RandSeed,EDX $0000003C
(60)
$00000001
(1)
$1
(1)
0 RandSeed = EDX = 1 ($1)
MUL EDX $0000003C
(60)
$00000000
(0)
$1
(1)
0 EDX * EAX = 1 * 60 = 60 ($3C)
EDX = $0, EAX = $3C
MOV Result,EDX $0000003C
(60)
$00000000
(0)
$1
(1)
0 Result = EDX = 0
Вывод: 1 число = 0, RandSeed = 1
2 MOV EAX,Range $0000003C
(60)
0 $1
(1)
0 EAX = Range = 60 ($3C)
IMUL EDX,RandSeed,$8088405 $0000003C
(60)
$08088405
(134775813)
$1
(1)
0 EDX = RandSeed * $8088405 = 1 * 134775813 = 134775813 ($8088405)
INC EDX $0000003C
(60)
$08088406
(134775814)
$1
(1)
0 EDX = EDX + 1 = 134775813 + 1 = 134775814 ($8088406)
MOV RandSeed,EDX $0000003C
(60)
$08088406
(134775814)
$8088406
(134775814)
0 RandSeed = EDX = 134775814 ($8088406)
MUL EDX $E1FEF168
(3791581544)
$00000001
(1)
$8088406
(134775814)
0 EDX * EAX = 134775814 * 60 = 8086548840 ($1E1FEF168)
EDX = $1, EAX = $E1FEF168
MOV Result,EDX $E1FEF168
(3791581544)
$00000001
(1)
$8088406
(134775814)
1 Result = EDX = 1
Вывод: 2 число = 1, RandSeed = 134775814
3 MOV EAX,Range $0000003C
(60)
0 $8088406
(134775814)
0 EAX = Range = 60 ($3C)
IMUL EDX,RandSeed,$8088405 $0000003C
(60)
$DC6DAC1E
(3698175006)
$8088406
(134775814)
0 EDX = RandSeed * $8088405 = 134775814 * 134775813 = 18164519904586782 ($408888DC6DAC1E)
Примечание. Старшее слово ($408888) нигде не записывается (оно не учитывается). В регистр EDX записываются только младшие разряды шестнадцатеричного числа.
INC EDX $0000003C
(60)
$DC6DAC1F
(3698175007)
$8088406
(134775814)
0 EDX = EDX + 1 = 3698175006 + 1 = 3698175007 ($DC6DAC1F)
MOV RandSeed,EDX $0000003C
(60)
$DC6DAC1F
(3698175007)
$DC6DAC1F
(-596792289)
0 RandSeed = EDX = -596792289 ($DC6DAC1F)
Примечание. Поскольку тип Integer принимает значения -2147483648..2147483647, то число будет занимать 4 байта. Т.к. число $DC6DAC1F = 3698175007 > 2147483647, в этом случае переменная RandSeed примет отрицательное значение: -596792289.
MUL EDX $A9B45744
(2847168324)
$00000033
(51)
$DC6DAC1F
(-596792289)
0 EDX * EAX = 3698175007 * 60 = 221890500420 ($33A9B45744)
EDX = $33, EAX = $A9B45744
MOV Result,EDX $A9B45744
(2847168324)
$00000033
(51)
$DC6DAC1F
(-596792289)
51 Result = EDX = 51
Вывод: 3 число = 51, RandSeed = -596792289
4 MOV EAX,Range $0000003C
(60)
0 $DC6DAC1F
(-596792289)
0 EAX = Range = 60 ($3C)
IMUL EDX,RandSeed,$8088405 $0000003C
(60)
$33DC589B
(870078619)
$DC6DAC1F
(-596792289)
0 EDX = RandSeed * $8088405 = -596792289 * 134775813 = <для корректной работы -596792289 заменим на 3698175007> = 3698175007 * 134775813 = 498424543184705691 ($6EAC27B33DC589B)
INC EDX $0000003C
(60)
$33DC589C
(870078620)
$DC6DAC1F
(-596792289)
0 EDX = EDX + 1 = 870078619 + 1 = 870078620 ($33DC589C)
MOV RandSeed,EDX $0000003C
(60)
$33DC589C
(870078620)
$33DC589C
(870078620)
0 RandSeed = EDX = 870078620 ($33DC589C)
MUL EDX $27A4C490
(665109648)
$0000000C
(12)
$33DC589C
(870078620)
0 EDX * EAX = 870078620 * 60 = 52204717200 ($C27A4C490)
EDX = $C, EAX = $27A4C490
MOV Result,EDX $27A4C490
(665109648)
$0000000C
(12)
$33DC589C
(870078620)
12 Result = EDX = 12
Вывод: 4 число = 12, RandSeed = 870078620
5 MOV EAX,Range $0000003C
(60)
0 $33DC589C
(870078620)
0 EAX = Range = 60 ($3C)
IMUL EDX,RandSeed,$8088405 $0000003C
(60)
$45DE2B0C
(1172187916)
$33DC589C
(870078620)
0 EDX = RandSeed * $8088405 = 870078620 * 134775813 = 117265553384418060 ($1A09C6645DE2B0C)
INC EDX $0000003C
(60)
$45DE2B0D
(1172187917)
$33DC589C
(870078620)
0 EDX = EDX + 1 = 1172187916 + 1 = 1172187917 ($45DE2B0D)
MOV RandSeed,EDX $0000003C
(60)
$45DE2B0D
(1172187917)
$45DE2B0D
(1172187917)
0 RandSeed = EDX = 1172187917 ($45DE2B0D)
MUL EDX $6012170C
(1611798284)
$00000010
(16)
$45DE2B0D
(1172187917)
0 EDX * EAX = 1172187917 * 60 = 70331275020 ($106012170C)
EDX = $10, EAX = $6012170C
MOV Result,EDX $6012170C
(1611798284)
$00000010
(16)
$45DE2B0D
(1172187917)
16 Result = EDX = 16
Вывод: 5 число = 16, RandSeed = 1172187917

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

Продолжение...

Категория: Программирование на Delphi | Добавил: newerow1989 (06.03.2017 09:38 )
Просмотров: 191 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Все смайлы
Код *:
Поиск
Друзья сайта
  • Создать сайт
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Все проекты компании
  • Copyright MyCorp © 2018
    Автор этого сайта: Неверов Евгений Викторович

    Мои координаты
    Бесплатный конструктор сайтов - uCozЯндекс.Метрика