Метод «Середин квадратов»

Свое название метод получил от арифметической операции возведения в квадрат, используемой при построении выборки. На самом деле в процессе вычислений получается последовательность больших целых чисел, которым ставятся в соответствие числа из интервала [0,1). Генератор работает в 4k-разрядной сетке, где k — целое число. В рассмотренном далее примере для простоты понимания используются 8-разрядные десятичные числа, а в программном фрагменте — двоичная 28-разрядная сетка.

Для получения последовательности необходимо задаться начальным числом-"затравкой" x₀ половинной разрядности (2k). Это число проще всего получить, прочитав показания часов реального времени компьютера. В выбранной разрядной сетке последовательность полностью определяется значением x₀. Для одинаковых x₀ всегда получается одна и та же последовательность. На каждом шаге текущее целое число x_i возводится в квадрат (при этом получается число разрядности 4k), и из центральных 2k разрядов полученного квадрата формируется новое целое число x_i+1. Числа u_i в диапазоне [0,1) получаются делением x_i на число М=100...0 (2k нулей, число записано в той же разрядной сетке, что используется при генерации; очевидно, что M на 1 больше максимального числа, представимого в 2k-разрядной сетке).

Этот метод проще разобрать на примере, чем изучать приведенное выше описание. Зададимся 8-разрядной десятичной сеткой, пусть начальное число 1349:

M=10 000 (1 и 4 нуля);

x₀=1349; u₀=0.1349; x₀²=01819801;

x₁=8198; u₁=0.8198; x₁²=67207204;

x₂=2072; u₂=0.2072; x₂²=04293184;

x₃=2931; u₃=0.2931; ...

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

56002034 à 0020 à 00000400 à 0004 à 00000016 à 0000)

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