Фильтр-генератор случайных чисел
Задача генерации последовательности случайных чисел заданного распределения и в заданном диапазоне по-прежнему остается нетривиальной, несмотря на достаточное количество исследований, посвященных данной теме. Проблема, в основном, заключается в том, что трудно построить универсальный генератор, подходящий для решения всех задач. Для каждого случая применение уже существующих алгоритмов генерации случайных чисел возможно лишь с некоторыми оговорками и ограничениями.
Используя далее в этой статье термин "случайная последовательность", мы, конечно же, будем говорить о последовательности псевдослучайных чисел, т.е. последовательности, подчиняющейся некоторому статистическому распределению, ибо понятно, что компьютерная программа, имея на входе детерминированные данные, не может сгенерировать истинно случайное число. На сегодняшний день существует лишь один известный автору генератор истинно случайных чисел – это пул энтропии ядра Linux. На программном уровне он представляет собой таблицу с данными о времени доступа того или иного процесса к функциям ядра (системным вызовам). Инициализируется он, естественно, лишь во время загрузки ядра (о чем можно прочесть сообщение во время загрузки системы) и "умирает" (выгружается) вместе с последним. Понятно, что, при всей своей "истинной случайности", для написания пользовательских программ он совершенно непригоден. Однако не лучше обстоит дело и с широко известными и давно используемыми генераторами.
Например, в классической монографии Кнута исследуется последовательность X случайных чисел, генерируемая рекуррентным соотношением
Xn=(a.Xn-1+c)mod m, (1)
где mod m означает операцию деления по модулю m (взятие остатка). Данная последовательность образует циклы длиной m и хорошо удовлетворяет статистическим критериям случайности. Таким образом, подобрав "хорошие" параметры a, X0, c и m, можно получить соответствующий генератор случайных чисел. Но на практике все оказывается не так просто.
Первая "мина" заложена в самом соотношении (1). Ведь рекурсия налагает свои ограничения и требует более внимательно относиться к размерам стека и структур данных, создаваемых во время работы программы. Например, при попытке генерации случайной последовательности длиной 512 чисел с помощью рекуррентного соотношения (1) в одной из программ виртуальная машина Java 2 выдала сообщение о переполнении стека уже после 51-го сгенерированного числа… И если при использовании C мы еще можем манипулировать стеком программы, то в Java это затруднительно (точнее, возможно до определенного предела). Вычислять каждый раз размер требуемого стека лишь для того, чтобы потом извлечь сгенерированные данные и разом этот стек "сложить" - неоправданное расточительство ресурсов и времени системы.
Вторая проблема заключается в поиске этих самых параметров a, X0, c, m. Если с m все ясно – он определяет длину цикла, а значит, и последовательности, то подбор трех остальных требует значительных усилий и времени, зависящих от требуемых статистических характеристик. Таким образом, лучше всего не полагаться на "проверенные" или "классические" генераторы, а внимательно изучить задачу и решить, возможно ли для данной конкретной цели построить и применить собственный. Возможно, он будет немного хуже по статистическим критериям, но полностью отвечать поставленной задаче и к тому же быстрее работать.
Постановка задачи.
Исходя из вышеизложенного, поставим перед собой следующую задачу:
Построить генератор целых случайных чисел, равномерно распределенных в интервале от 1 до 256.
Вначале определимся с терминологией. Со "случайностью" все ясно – выше уже указывалось, что мы создаем генератор псевдослучайных чисел с определенными статистическими критериями. Одним из этих критериев является равномерное распределение сгенерированных чисел. Напомню, что при нем функция плотности распределения постоянна, т.е. для любого элемента последовательности вероятность попадания в заданный промежуток одна и та же. Но существует еще одна важная характеристика случайной последовательности – статистическая независимость полученных случайных чисел. Она, как известно, означает, что вероятность попадания двух чисел в заданный диапазон равна произведению вероятностей попадания этих чисел в этот диапазон. Статистическую независимость мы оценим позднее, после получения вида последовательности.
Для уже сгенерированной последовательности мы впоследствии вычислим коэффициент корреляции и увидим, насколько независимы полученные значения. Этот коэффициент мы будем вычислять по следующей формуле, хорошо известной из математической статистики:
n(X0X1+X1X2+…+Xn-2Xn-1+…+Xn-1X0)-(Sxn)І
K=--------------------------------------- (2),
n(SxnІ)-(Sxn)І
где X0…Xn-1 – члены последовательности,
n – их число.
Чем меньше K отличается от нуля, тем более удовлетворительна независимость случайной последовательности.
Вычисление коэффициента корреляции, конечно, необходимо, но мы строим свой генератор и должны разработать собственные критерии его пригодности. Движение в обратном направлении – сначала программа, а затем ее математическое обоснование – невозможно, и это в свое время доказано Кнутом, Виртом и другими отцами теории алгоритмов. Поэтому далее мы скрупулезно будем доказывать как саму возможность существования некоторого генератора случайных чисел, так и его свойства.
Введем понятие линейной независимости последовательности. Определение, которое мы примем, несколько отличается от некоторых других, в частности от того, которое используется, например, у Кнута, но, как мы увидим далее, для нашей цели его вполне достаточно, и применять более сильное нам ни к чему.
Итак:
Последовательность случайных чисел U линейно независима, если не существует таких двух чисел a и b,что для всех U(n) из U выполняется равенство:
U(n)= a+b.n (3)
Геометрически (3) представляет собой не что иное, как уравнение прямой на плоскости, и, казалось бы, такой "слабый" критерий не может быть достаточным для оценки независимости последовательности. Но он хорошо подойдет для решения нашей задачи.
Итак, перед нами стоит задача построения генератора линейно независимой последовательности целых случайных чисел, равномерно распределенных в интервале от 1 до 256.
Обоснование решения
Для решения поставленной задачи определим вначале на множестве целых чисел операцию их свертки. Термин "свертка" намеренно взят мною из теории цифровой обработки сигналов. Там он описывает процесс пропускания сигнала через фильтр и определяется следующим образом (в случае дискретного сигнала):
G (x)=Sf (x) h (x-t) (4),
N
где f (x) – исходный сигнал,
h (x) – функция фильтра, сдвинутая в (4) на время t,
g (x) – полученный сигнал,
N – число отсчетов.
В случае непрерывного сигнала простая сумма в (4) заменяется на интегральную. Грубо говоря, мы просто двигаем два сигнала навстречу друг другу и на каждом отсчете замеряем их интегральную сумму. На выходе мы получаем отфильтрованный сигнал с заданными свойствами.
Определим теперь операцию свертки двух целых чисел.
Пусть a и b – целые числа, a0a1…an-1 и b0b1…bn-1- их двоичные представления. Сверткой чисел a и b назовем целое число c с двоичным
представлением c0c1…cn-1, такое, что
ci=ai|bn-1-i, i=[0…n-1] (5),
где "|" означает, конечно же, логическое "или". Видно, что выражение (5) представляет собой видоизмененное (4), где операция произведения заменена на логическое "или", а роль суммирования выполняет сложение весов соответствующих битов, т.е. переход к десятичному представлению. Так что суть операции свертки – фильтрация – оставлена нами без изменений, что и отражено в условном названии нашего генератора в заголовке статьи. Почему именно свертка сигналов была взята в качестве физического прообраза генератора?
Знакомым с цифровой обработкой сигналов известно, что операции свертки и вычисления спектра (например, спектра Фурье) взаимно обратимы, т.е. свертка сигналов равна произведению спектров, и наоборот. Это значит, что с помощью этой операции можно получить сигнал с требуемым спектром, а если мы исследуем случайный сигнал – с требуемым распределением.
Теперь необходимо изучить некоторые свойства введенной нами операции свертки. Для этого сформулируем и докажем лемму.
Лемма. Последовательность чисел сn, получаемая в результате операции свертки (5), где аi принимает последовательные значения от 1 до 256, линейно независима.
Доказательство. (Нестрогое). Предположим обратное, т.е. что существуют такие два числа a и b, что выполняется равенство (3). Но тогда a в этом равенстве изменяет все значения n, а не только те, в которых отсутствует соответствующий значащий бит, что противоречит смыслу операции логическое "или". Следовательно, наше предположение неверно, и последовательность, получаемая в результате операции (4),линейно независима. (Строгое).Как известно из курса линейной алгебры, система n векторов x1,x2,…,xn в n-мерном линейном пространстве является линейно зависимой, если существуют такие n чисел a1,a2,…,an, одновременно не равные нулю, что выполняется равенство
a1x1+a2x2+…+anxn=0 (*)
Очевидно, что в случае последовательности, получаемой при помощи свертки, соотношение (*) будет выполняться именно при равенстве коэффициентов a1,a2,…,an нулю, причем всех одновременно. Поэтому последовательность сn линейно независима. ?
Строгое доказательство приведено для подтверждения "законности" введения нами понятия линейной зависимости двух чисел.
Теперь поговорим о статистической независимости последовательности, полученной в результате операции свертки (5).Исходная последовательность чисел a(n) представляет собой просто ряд целых от 0 до 255, и здесь речь о какой-либо независимости, а значит, и случайности, идти не может. Обладает ли полученная последовательность требуемыми свойствами? Не прибегая к громоздким выкладкам, рассмотрим внимательно, как вычисляется свертка (5).На каждой итерации операция логического "или" включает (устанавливает в 1) те незначащие (нулевые) биты в двоичном представлении числа, которые попадают под значащий бит маски. Эта операция соответствует увеличению исходного числа на вес текущего для данной итерации бита. Но это увеличение происходит лишь при условии
a mod 2?>=0,
где a-исходное число,
n-номер бита.
При этом обход битового массива маской осуществляется в направлении, обратном собственному расположению битов маски, иначе мы получили бы ступенчато возрастающую последовательность. Это означает, что при выборе маски определенным образом можно достичь требуемой корреляции последовательности. Выбор маски – это тема отдельной статьи и здесь рассматриваться не будет.
Таким образом, используя введенную нами операцию свертки, мы можем получить линейно и статистически независимую последовательность целых чисел в заданном интервале.
Реализация генератора случайных чисел
Реализовать описанный выше генератор можно, конечно, на любом языке, но для тестирования предпочтительно "обрушить" на решение этой задачи всю мощь C++. Вначале опишем основную структуру данных. Это класс, определяющий собственно случайное значение.
class randomValue
{
private:
int cnt;
void getbin(int n,int div);
public:
randomValue(int n) ;
randomValue();
int num;
int* bin_buffer;
void get_decimal();
}
Класс имеет два конструктора. Вот их реализация:
randomValue::randomValue(int n)
{
num=n;
this->cnt=0;
this->bin_buffer=new int[8];
this->getbin(this->num,128) ;
}
randomValue::randomValue()
{
this->num=0;
this->cnt=0;
this->bin_buffer=new int[8];
}
Второй конструктор и создает объект, содержащий случайное значение. Его поле num,предназначенное для его хранения, пока равно нулю, и будет заполнено позднее в результате операции свертки.
Функции getbin() и get_decimal() просто осуществляют преобразование числа из десятичного представления в двоичное и обратно.
void randomValue::getbin(int n,int div)
{
int rest;
if(div>=1)
{
if( (rest=n-div)>=0)
{
this->bin_buffer[cnt]=1;
cnt++;
getbin(rest,div/2);}
else {
this->bin_buffer[cnt]=0;
cnt++;
getbin(n,div/2);
}
}
}
void randomValue::get_decimal()
{
int st=1;
this->num=0;
for (int i=7;i>=0;i--)
{
this->num+=this->bin_buffer[i]*st;
st*=2;
}
this->cnt=0;
std::cout<<this->num<<" ";
}
Поле * bin_buffer –это указатель на буфер, в котором будет храниться двоичное значение случайного числа, вычисляемое функцией
getbin().Следующий оператор вычисляет свертку двух целых чисел.
randomValue* operator + (randomValue rnd,randomValue mask)
{
randomValue* r=new randomValue();
for(int i=0;i<=7;i++)
{
int t=rnd.bin_buffer[7-i]|mask.bin_buffer[i];
r->bin_buffer[i]=t;
}
r->get_decimal();
return r;
}
Второй параметр операторной функции – это маска, которая будет накладываться на исходное значение для получения случайного. В терминах цифровой обработки сигналов, это и есть фильтр, через который будет пропускаться исходная последовательность. Очевидно, для получения "хорошей" случайной последовательности для маски следует выбирать число с одним значащим битом в двоичном представлении. Работа оператора состоит в последовательном заполнении буфера * bin_buffer значениями, полученными в результате свертки. Далее вычисляется соответствующее двоичное значение при помощи функции get_decimal(). Оператор возвращает указатель на новый объект randomValue.
Теперь посмотрим, как все это работает. Вот как будет выглядеть тело функции, генерирующей случайную последовательность:
vector <randomValue*> rand_vector;
randomValue *filter=new randomValue(2);
int size=256;
for(int n=0;n<size;n++)
{
randomValue *r=new randomValue(n);
randomValue *res=*r+*filter;
rand_vector.push_back(res);
delete r;
}
delete filter;
Вначале мы определяем вектор, в котором будут храниться указатели на создаваемые объекты randomValue. Затем мы задаем маску (она в данном примере равна 2) и в цикле заполняем вектор случайными значениями, выполняя на каждой итерации свертку исходного числа с маской. Заметим, что в качестве исходной нами выбрана как можно более "неслучайная" последовательность – просто ряд чисел от 0 до 255. В результате получены следующие значения:
2 130 66 194 34 162 98 226 18 146 82 210 50 178 114 242 10 138 74 202 42 170 106 234 26 154 90 218 58 186 122 250 6 134 70 198 38 166 102 230 22 150 86 214 54 182 118 246 14 142 78 206 46 174 110 238 30 158 94 222 62 190 126 254 2 130 66 194 34 162 98 226 18 146 82 210 50 178 114 242 10 138 74 202 42 170 106 234 26 154 90 218 58 186 122 250 6 134 70 198 38 166 102 230 22 150 86 214 54 182 118 246 14 142 78 206 46 174 110 238 30 158 94 222 62 190 126 254 3 131 67 195 35 163 99 227 19 147 83 211 51 179 115 243 11 139 75 203 43 171 107 235 27 155 91 219 59 187 123 251 7 135 71 199 39 167 103 231 23 151 87 215 55 183 119 247 15 143 79 207 47 175 111 239 31 159 95 223 63 191 127 255 3 131 67 195 35 163 99 227 19 147 83 211 51 179 115 243 11 139 75 203 43 171 107 235 27 155 91 219 59 187 123 251 7 135 71 199 39 167 103 231 23 151 87 215 55 183 119 247 15 143 79 207 47 175 111 239 31 159 95 223 63 191 127 255
Даже с первого взгляда ясно, что эта последовательность может удовлетворить самым жестким требованиям случайности. Коэффициент ее корреляции, вычисленный с помощью (2), настолько мал, что компилятор "отказывается" хранить столь длинное число с плавающей точкой и просто обращает его в нуль. Поэтому дополнительного улучшения статистических параметров она не требует.
Оценка алгоритмической сложности генератора
Очевидно, алгоритм в общем случае имеет квадратичное время исполнения, т.е. сложность порядка O(nІ). Однако битовые операции "или", выполняющиеся крайне быстро (за 1 такт процессора), используют для генерации одного случайного числа, соответственно, 8 тактов, и это значение постоянно. Поэтому можно сказать, что алгоритм имеет линейное время исполнения, равное 8.N, где N – длина требуемой последовательности.
Заключение
Мы построили небольшой по объему кода и достаточно быстрый генератор случайных чисел, который может использоваться при решении многих прикладных задач. Помимо этого, мы увидели, что реализации должна предшествовать большая подготовительная работа, связанная с анализом (если не математическим, то хотя бы качественным) поставленной задачи и возможности ее решения – это поможет избежать бессмысленного написания сотен строк неработающего кода. Кроме этого, совершенно необходимо изучить некоторые источники по данной теме. Интересующимся генерацией случайных последовательностей могу порекомендовать две основные книги. Первая, конечно, все та же монография Кнута "Искусство программирования", т.2. Вторая – это прекрасная книга немецкого математика и программиста Брандта "Анализ данных", недавно вышедшая в бумажном варианте.
Автор будет признателен всем, кто пришлет свои отзывы и предложения, а также вопросы, ни один из которых не останется без ответа. Особо будут приветствоваться новые идеи о генерации случайных последовательностей.
Вадим Шандриков, qnx999@tut.by
Используя далее в этой статье термин "случайная последовательность", мы, конечно же, будем говорить о последовательности псевдослучайных чисел, т.е. последовательности, подчиняющейся некоторому статистическому распределению, ибо понятно, что компьютерная программа, имея на входе детерминированные данные, не может сгенерировать истинно случайное число. На сегодняшний день существует лишь один известный автору генератор истинно случайных чисел – это пул энтропии ядра Linux. На программном уровне он представляет собой таблицу с данными о времени доступа того или иного процесса к функциям ядра (системным вызовам). Инициализируется он, естественно, лишь во время загрузки ядра (о чем можно прочесть сообщение во время загрузки системы) и "умирает" (выгружается) вместе с последним. Понятно, что, при всей своей "истинной случайности", для написания пользовательских программ он совершенно непригоден. Однако не лучше обстоит дело и с широко известными и давно используемыми генераторами.
Например, в классической монографии Кнута исследуется последовательность X случайных чисел, генерируемая рекуррентным соотношением
Xn=(a.Xn-1+c)mod m, (1)
где mod m означает операцию деления по модулю m (взятие остатка). Данная последовательность образует циклы длиной m и хорошо удовлетворяет статистическим критериям случайности. Таким образом, подобрав "хорошие" параметры a, X0, c и m, можно получить соответствующий генератор случайных чисел. Но на практике все оказывается не так просто.
Первая "мина" заложена в самом соотношении (1). Ведь рекурсия налагает свои ограничения и требует более внимательно относиться к размерам стека и структур данных, создаваемых во время работы программы. Например, при попытке генерации случайной последовательности длиной 512 чисел с помощью рекуррентного соотношения (1) в одной из программ виртуальная машина Java 2 выдала сообщение о переполнении стека уже после 51-го сгенерированного числа… И если при использовании C мы еще можем манипулировать стеком программы, то в Java это затруднительно (точнее, возможно до определенного предела). Вычислять каждый раз размер требуемого стека лишь для того, чтобы потом извлечь сгенерированные данные и разом этот стек "сложить" - неоправданное расточительство ресурсов и времени системы.
Вторая проблема заключается в поиске этих самых параметров a, X0, c, m. Если с m все ясно – он определяет длину цикла, а значит, и последовательности, то подбор трех остальных требует значительных усилий и времени, зависящих от требуемых статистических характеристик. Таким образом, лучше всего не полагаться на "проверенные" или "классические" генераторы, а внимательно изучить задачу и решить, возможно ли для данной конкретной цели построить и применить собственный. Возможно, он будет немного хуже по статистическим критериям, но полностью отвечать поставленной задаче и к тому же быстрее работать.
Постановка задачи.
Исходя из вышеизложенного, поставим перед собой следующую задачу:
Построить генератор целых случайных чисел, равномерно распределенных в интервале от 1 до 256.
Вначале определимся с терминологией. Со "случайностью" все ясно – выше уже указывалось, что мы создаем генератор псевдослучайных чисел с определенными статистическими критериями. Одним из этих критериев является равномерное распределение сгенерированных чисел. Напомню, что при нем функция плотности распределения постоянна, т.е. для любого элемента последовательности вероятность попадания в заданный промежуток одна и та же. Но существует еще одна важная характеристика случайной последовательности – статистическая независимость полученных случайных чисел. Она, как известно, означает, что вероятность попадания двух чисел в заданный диапазон равна произведению вероятностей попадания этих чисел в этот диапазон. Статистическую независимость мы оценим позднее, после получения вида последовательности.
Для уже сгенерированной последовательности мы впоследствии вычислим коэффициент корреляции и увидим, насколько независимы полученные значения. Этот коэффициент мы будем вычислять по следующей формуле, хорошо известной из математической статистики:
n(X0X1+X1X2+…+Xn-2Xn-1+…+Xn-1X0)-(Sxn)І
K=--------------------------------------- (2),
n(SxnІ)-(Sxn)І
где X0…Xn-1 – члены последовательности,
n – их число.
Чем меньше K отличается от нуля, тем более удовлетворительна независимость случайной последовательности.
Вычисление коэффициента корреляции, конечно, необходимо, но мы строим свой генератор и должны разработать собственные критерии его пригодности. Движение в обратном направлении – сначала программа, а затем ее математическое обоснование – невозможно, и это в свое время доказано Кнутом, Виртом и другими отцами теории алгоритмов. Поэтому далее мы скрупулезно будем доказывать как саму возможность существования некоторого генератора случайных чисел, так и его свойства.
Введем понятие линейной независимости последовательности. Определение, которое мы примем, несколько отличается от некоторых других, в частности от того, которое используется, например, у Кнута, но, как мы увидим далее, для нашей цели его вполне достаточно, и применять более сильное нам ни к чему.
Итак:
Последовательность случайных чисел U линейно независима, если не существует таких двух чисел a и b,что для всех U(n) из U выполняется равенство:
U(n)= a+b.n (3)
Геометрически (3) представляет собой не что иное, как уравнение прямой на плоскости, и, казалось бы, такой "слабый" критерий не может быть достаточным для оценки независимости последовательности. Но он хорошо подойдет для решения нашей задачи.
Итак, перед нами стоит задача построения генератора линейно независимой последовательности целых случайных чисел, равномерно распределенных в интервале от 1 до 256.
Обоснование решения
Для решения поставленной задачи определим вначале на множестве целых чисел операцию их свертки. Термин "свертка" намеренно взят мною из теории цифровой обработки сигналов. Там он описывает процесс пропускания сигнала через фильтр и определяется следующим образом (в случае дискретного сигнала):
G (x)=Sf (x) h (x-t) (4),
N
где f (x) – исходный сигнал,
h (x) – функция фильтра, сдвинутая в (4) на время t,
g (x) – полученный сигнал,
N – число отсчетов.
В случае непрерывного сигнала простая сумма в (4) заменяется на интегральную. Грубо говоря, мы просто двигаем два сигнала навстречу друг другу и на каждом отсчете замеряем их интегральную сумму. На выходе мы получаем отфильтрованный сигнал с заданными свойствами.
Определим теперь операцию свертки двух целых чисел.
Пусть a и b – целые числа, a0a1…an-1 и b0b1…bn-1- их двоичные представления. Сверткой чисел a и b назовем целое число c с двоичным
представлением c0c1…cn-1, такое, что
ci=ai|bn-1-i, i=[0…n-1] (5),
где "|" означает, конечно же, логическое "или". Видно, что выражение (5) представляет собой видоизмененное (4), где операция произведения заменена на логическое "или", а роль суммирования выполняет сложение весов соответствующих битов, т.е. переход к десятичному представлению. Так что суть операции свертки – фильтрация – оставлена нами без изменений, что и отражено в условном названии нашего генератора в заголовке статьи. Почему именно свертка сигналов была взята в качестве физического прообраза генератора?
Знакомым с цифровой обработкой сигналов известно, что операции свертки и вычисления спектра (например, спектра Фурье) взаимно обратимы, т.е. свертка сигналов равна произведению спектров, и наоборот. Это значит, что с помощью этой операции можно получить сигнал с требуемым спектром, а если мы исследуем случайный сигнал – с требуемым распределением.
Теперь необходимо изучить некоторые свойства введенной нами операции свертки. Для этого сформулируем и докажем лемму.
Лемма. Последовательность чисел сn, получаемая в результате операции свертки (5), где аi принимает последовательные значения от 1 до 256, линейно независима.
Доказательство. (Нестрогое). Предположим обратное, т.е. что существуют такие два числа a и b, что выполняется равенство (3). Но тогда a в этом равенстве изменяет все значения n, а не только те, в которых отсутствует соответствующий значащий бит, что противоречит смыслу операции логическое "или". Следовательно, наше предположение неверно, и последовательность, получаемая в результате операции (4),линейно независима. (Строгое).Как известно из курса линейной алгебры, система n векторов x1,x2,…,xn в n-мерном линейном пространстве является линейно зависимой, если существуют такие n чисел a1,a2,…,an, одновременно не равные нулю, что выполняется равенство
a1x1+a2x2+…+anxn=0 (*)
Очевидно, что в случае последовательности, получаемой при помощи свертки, соотношение (*) будет выполняться именно при равенстве коэффициентов a1,a2,…,an нулю, причем всех одновременно. Поэтому последовательность сn линейно независима. ?
Строгое доказательство приведено для подтверждения "законности" введения нами понятия линейной зависимости двух чисел.
Теперь поговорим о статистической независимости последовательности, полученной в результате операции свертки (5).Исходная последовательность чисел a(n) представляет собой просто ряд целых от 0 до 255, и здесь речь о какой-либо независимости, а значит, и случайности, идти не может. Обладает ли полученная последовательность требуемыми свойствами? Не прибегая к громоздким выкладкам, рассмотрим внимательно, как вычисляется свертка (5).На каждой итерации операция логического "или" включает (устанавливает в 1) те незначащие (нулевые) биты в двоичном представлении числа, которые попадают под значащий бит маски. Эта операция соответствует увеличению исходного числа на вес текущего для данной итерации бита. Но это увеличение происходит лишь при условии
a mod 2?>=0,
где a-исходное число,
n-номер бита.
При этом обход битового массива маской осуществляется в направлении, обратном собственному расположению битов маски, иначе мы получили бы ступенчато возрастающую последовательность. Это означает, что при выборе маски определенным образом можно достичь требуемой корреляции последовательности. Выбор маски – это тема отдельной статьи и здесь рассматриваться не будет.
Таким образом, используя введенную нами операцию свертки, мы можем получить линейно и статистически независимую последовательность целых чисел в заданном интервале.
Реализация генератора случайных чисел
Реализовать описанный выше генератор можно, конечно, на любом языке, но для тестирования предпочтительно "обрушить" на решение этой задачи всю мощь C++. Вначале опишем основную структуру данных. Это класс, определяющий собственно случайное значение.
class randomValue
{
private:
int cnt;
void getbin(int n,int div);
public:
randomValue(int n) ;
randomValue();
int num;
int* bin_buffer;
void get_decimal();
}
Класс имеет два конструктора. Вот их реализация:
randomValue::randomValue(int n)
{
num=n;
this->cnt=0;
this->bin_buffer=new int[8];
this->getbin(this->num,128) ;
}
randomValue::randomValue()
{
this->num=0;
this->cnt=0;
this->bin_buffer=new int[8];
}
Второй конструктор и создает объект, содержащий случайное значение. Его поле num,предназначенное для его хранения, пока равно нулю, и будет заполнено позднее в результате операции свертки.
Функции getbin() и get_decimal() просто осуществляют преобразование числа из десятичного представления в двоичное и обратно.
void randomValue::getbin(int n,int div)
{
int rest;
if(div>=1)
{
if( (rest=n-div)>=0)
{
this->bin_buffer[cnt]=1;
cnt++;
getbin(rest,div/2);}
else {
this->bin_buffer[cnt]=0;
cnt++;
getbin(n,div/2);
}
}
}
void randomValue::get_decimal()
{
int st=1;
this->num=0;
for (int i=7;i>=0;i--)
{
this->num+=this->bin_buffer[i]*st;
st*=2;
}
this->cnt=0;
std::cout<<this->num<<" ";
}
Поле * bin_buffer –это указатель на буфер, в котором будет храниться двоичное значение случайного числа, вычисляемое функцией
getbin().Следующий оператор вычисляет свертку двух целых чисел.
randomValue* operator + (randomValue rnd,randomValue mask)
{
randomValue* r=new randomValue();
for(int i=0;i<=7;i++)
{
int t=rnd.bin_buffer[7-i]|mask.bin_buffer[i];
r->bin_buffer[i]=t;
}
r->get_decimal();
return r;
}
Второй параметр операторной функции – это маска, которая будет накладываться на исходное значение для получения случайного. В терминах цифровой обработки сигналов, это и есть фильтр, через который будет пропускаться исходная последовательность. Очевидно, для получения "хорошей" случайной последовательности для маски следует выбирать число с одним значащим битом в двоичном представлении. Работа оператора состоит в последовательном заполнении буфера * bin_buffer значениями, полученными в результате свертки. Далее вычисляется соответствующее двоичное значение при помощи функции get_decimal(). Оператор возвращает указатель на новый объект randomValue.
Теперь посмотрим, как все это работает. Вот как будет выглядеть тело функции, генерирующей случайную последовательность:
vector <randomValue*> rand_vector;
randomValue *filter=new randomValue(2);
int size=256;
for(int n=0;n<size;n++)
{
randomValue *r=new randomValue(n);
randomValue *res=*r+*filter;
rand_vector.push_back(res);
delete r;
}
delete filter;
Вначале мы определяем вектор, в котором будут храниться указатели на создаваемые объекты randomValue. Затем мы задаем маску (она в данном примере равна 2) и в цикле заполняем вектор случайными значениями, выполняя на каждой итерации свертку исходного числа с маской. Заметим, что в качестве исходной нами выбрана как можно более "неслучайная" последовательность – просто ряд чисел от 0 до 255. В результате получены следующие значения:
2 130 66 194 34 162 98 226 18 146 82 210 50 178 114 242 10 138 74 202 42 170 106 234 26 154 90 218 58 186 122 250 6 134 70 198 38 166 102 230 22 150 86 214 54 182 118 246 14 142 78 206 46 174 110 238 30 158 94 222 62 190 126 254 2 130 66 194 34 162 98 226 18 146 82 210 50 178 114 242 10 138 74 202 42 170 106 234 26 154 90 218 58 186 122 250 6 134 70 198 38 166 102 230 22 150 86 214 54 182 118 246 14 142 78 206 46 174 110 238 30 158 94 222 62 190 126 254 3 131 67 195 35 163 99 227 19 147 83 211 51 179 115 243 11 139 75 203 43 171 107 235 27 155 91 219 59 187 123 251 7 135 71 199 39 167 103 231 23 151 87 215 55 183 119 247 15 143 79 207 47 175 111 239 31 159 95 223 63 191 127 255 3 131 67 195 35 163 99 227 19 147 83 211 51 179 115 243 11 139 75 203 43 171 107 235 27 155 91 219 59 187 123 251 7 135 71 199 39 167 103 231 23 151 87 215 55 183 119 247 15 143 79 207 47 175 111 239 31 159 95 223 63 191 127 255
Даже с первого взгляда ясно, что эта последовательность может удовлетворить самым жестким требованиям случайности. Коэффициент ее корреляции, вычисленный с помощью (2), настолько мал, что компилятор "отказывается" хранить столь длинное число с плавающей точкой и просто обращает его в нуль. Поэтому дополнительного улучшения статистических параметров она не требует.
Оценка алгоритмической сложности генератора
Очевидно, алгоритм в общем случае имеет квадратичное время исполнения, т.е. сложность порядка O(nІ). Однако битовые операции "или", выполняющиеся крайне быстро (за 1 такт процессора), используют для генерации одного случайного числа, соответственно, 8 тактов, и это значение постоянно. Поэтому можно сказать, что алгоритм имеет линейное время исполнения, равное 8.N, где N – длина требуемой последовательности.
Заключение
Мы построили небольшой по объему кода и достаточно быстрый генератор случайных чисел, который может использоваться при решении многих прикладных задач. Помимо этого, мы увидели, что реализации должна предшествовать большая подготовительная работа, связанная с анализом (если не математическим, то хотя бы качественным) поставленной задачи и возможности ее решения – это поможет избежать бессмысленного написания сотен строк неработающего кода. Кроме этого, совершенно необходимо изучить некоторые источники по данной теме. Интересующимся генерацией случайных последовательностей могу порекомендовать две основные книги. Первая, конечно, все та же монография Кнута "Искусство программирования", т.2. Вторая – это прекрасная книга немецкого математика и программиста Брандта "Анализ данных", недавно вышедшая в бумажном варианте.
Автор будет признателен всем, кто пришлет свои отзывы и предложения, а также вопросы, ни один из которых не останется без ответа. Особо будут приветствоваться новые идеи о генерации случайных последовательностей.
Вадим Шандриков, qnx999@tut.by
Компьютерная газета. Статья была опубликована в номере 36 за 2007 год в рубрике программирование
