Недавно мне пришла в голову идея поковыряться в недрах редактора скриптового языка VBA, вшитого внутрь старой доброй Excel. Конечно, ни для кого не является секретом, что продукты корпорации Microsoft таят в себе поистине бездонные глубины, и эти глубины могут затянуть в себя каждого неосторожного их исследователя. Казалось бы — всем давно известный (в узких кругах, конечно) VBA, застывший в своем развитии язык. Что там еще можно откопать? Спойлер: откопать что-то новое там вряд ли что‑то возможно, но вот копнуть поглубже — это возможно.

Примерно так же рассуждал и я, когда нажимал две клавиши Alt+F11, после того как открыл новую книгу до боли знакомой Excel»ки. Моей целью было вбить простенький код из самоучителя по VBA и немного поиграться с ним. Посмотреть, что выдаст программа — если выражаться студенческим языком, сделать обычную лабораторную работу. И в этот момент мне на глаза попалась функция Rnd(), которая, как сообщает справка Microsoft, возвращает значение, содержащее псевдослучайное число.

На тот момент ничто не предвещало какой‑либо опасности. Да, генератор псевдослучайных чисел, вшитый в VBA — простой линейный конгруэнтный алгоритм. Ничего особенного, казалось бы. И именно в этот момент меня угораздило заглянуть в кроличью нору, глубины которой оказались довольно внушительными.

Возможно, читателя также заинтересует вопрос о том, насколько глубока эта кроличья нора. Если это так, то приглашаю заглянуть туда вместе — не исключено, что нам все‑таки удастся добраться до ее дна. При этом никто не гарантирует (даже автор), что в этот момент снизу не постучат...

Немного теории

Если у нас есть последовательность действительно случайных чисел, мы никогда с точностью не сможем предсказать, какое число у нас «появится» следующим. Максимум, что мы сможем делать — на основе некоторого анализа с большей или меньшей степени достоверности попытаться его предсказать.

Если мы имеем дело с псевдослучайными числами, то зная законы их появления, мы с легкостью (относительной) сможем вычислить любое следующее число в последовательности. Линейный конгруэнтный алгоритм (или метод) (далее, ЛКМ) — это один из способов получить последовательность псевдослучайных чисел.

Сам способ вычисления псевдослучайных чисел при помощи ЛКМ довольно прост. У нас есть четыре целых числа:

• m — модуль или делитель (modulus);

• a — множитель (multiplier);

• с — приращение (increment);

• x₀ — начальное значение (seed).

Сама формула, по которой вычисляются псевдослучайные числа, выглядит так:

x1 = (x0 * a + c ) MOD m.

То есть, мы находим остаток при целочисленном делении числа (x₀ * a + c) на m . Этот остаток и есть наше псевдослучайное число. Далее мы ставим вычисленный x₁ на место x₀ и получаем второе число в последовательности. Теоретически, мы можем повторять подобную операцию вплоть до бесконечности, поскольку максимальная длина такой последовательности равняется делителю.

Это значит, что если мы возьмем максимально большой делитель, мы можем получить максимально большую последовательность уникальных чисел. Это понятно, поскольку если у нас есть определенный целый делитель, то теоретически мы можем работать с количеством остатков, равным самому модулю. А если мы можем получить столько остатков, то все они могут рано или поздно присутствовать на месте x₀.

Например, число 100 даёт 100 остатков от 0 до 99 (остаток 100 мы получить никак не сможем, надеюсь, что это вполне очевидно). Соответственно, если делитель будет равен 100, то и максимальная длина последовательности будет равна 100. Если длина последовательности в этом случае у нас будет равна 100, то 101-й ее член будет равен первому, 102-й — второму, и т. д. Таким образом, начиная со 101-члена, мы получим новый виток цикла, и так до бесконечности.

В то же время мы можем и не получить максимальную длину последовательности – все зависит от того, насколько хорошо подобраны задающие ее числа. Более подробно обо всех тонкостях задачи последовательностей при использовании ЛКМ можно посмотреть в той же Вики.

Немного о терминах

Целое число a называют сравнимым по некоторому модулю m (m — целое число) с числом b, в том случае, если при делении на m оба числа a и b дают одинаковый остаток. Это записывается так: a ≡  b (mod m).

Итак, числа 23 и 103 дают остаток 3 при делении на 10, значит 23 сравнимо со 103 по модулю 10 (23 ≡  103 (mod 10)). 

Таким образом, в русскоязычной математической литературе у термина «модуль» есть два значения:

• абсолютное значение числа;

• делитель в арифметике остатков.

Мне не ясно, почему абсолютное значение у нас называют «модулем». В той же англоязычной литературе абсолютное значение так и передается — absolute [value]. Если у кого‑либо из уважаемых читателей есть ответ на то, почему русскоязычный термин «модуль» имеет как минимум два математических значения, то его всегда можно написать внизу в комментариях — не стесняйтесь.

Теперь перейдем к вопросу о том, почему алгоритм называется конгруэнтным. Само понятие конгруэнтности весьма и весьма многозначное, своё значение этот термин имеет и в анатомии, и в психологии. Но если взять сферу, более близкую к теме данного исследования, то в математике понятие конгруэнтности можно встретить в геометрии. Как говорит вся та же Вики, конгруэнтность — это отношение эквивалентности на множестве геометрических фигур. Как, я надеюсь, известно читателям, символ «≡» также означает эквивалентность.

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

Итак, можно сказать, что самым часто приводящимся в примером отношения эквивалентности является сравнимость двух чисел по модулю. Таким образом, сравнимость по модулю является частным случаем такого отношения. Вот это уже намного ближе и информативнее. В английском языке все еще более прозрачнее, фраза «a и b сравнимы по модулю m» так и звучит: a and b are congruent modulo m.  

Так почему алгоритм именно конгруэнтный? А всё дело в том, что при его работе вычисляются два числа, сравнимые по некоторому модулю.   

Первое число — это выражение в скобках: (x₀ * a + c ). Второе число (x₁) — это остаток от деления первого числа на некоторый модуль:

x1 = (x0 * a + c ) MOD m.

То есть, мы можем написать: (x0*a + c ) ≡ ((x0*a + c ) MOD m) (mod m),
где MOD m – операция вычисления остатка при делении некоторого целого числа на другое целое число m (целочисленное деление).    

ЛКМ в VBA Excel

Итак, разобравшись с теорией и терминологией, можно переходить к практике. Согласно Вики, в VBA используется алгоритм со следующими параметрами:
а (множитель) — 1140671485 (43FD43FD₁₆);
с (приращение) — 12820163 (C39EC3₁₆);
m (модуль) — 2²⁴ (16777216 или 1000000₁₆).

Для того, чтобы избежать неопределенности, скажу, что числа, записанные «как есть» без всяких дополнительных постфиксов — всегда будут означать числа в десятичной системе счисления. А числа с постфиксом ₁₆ будут означать числа в 16-ричной системе счисления. Если кто-то предпочитает для этого использовать _hex, прошу сильно не ругаться...

А источник этих данных — старая ныне недоступная справка Microsoft, копия страницы которой доступна в цифровом архиве.

Оттуда же мы берем и начальное значение x₀ — 327680 (5000₁₆).

В то же время некоторые другие источники (например, этот) дают другое значение множителя: 16598013 (FD43FD₁₆).

Сравнивая эти два значения — 1140671485 (43FD43FD₁₆) и 16598013 (FD43FD₁₆) можно заметить, что в 16-ричном представлении оба эти числа имеют одинаковые 6 последних разрядов. При этом оба они дадут одинаковый остаток при делении на 2²⁴ (1000000₁₆).

В 16-ричном представлении это видно особенно наглядно. Понятно, что 16598013 при делении на 16777216 даст остаток 16598013 (FD43FD₁₆). Но и 43FD43FD₁₆ при делении на 1000000₁₆  даст такой же остаток (FD43FD₁₆). Для наилучшего понимания:

43FD43FD16 = 4316*100000016 + FD43FD16.

Соответственно, по правилам модульной арифметики оба числа (и 1140671485, и 16598013) могут с одинаковым успехом использоваться в уже указанном алгоритме VBA. То есть, в качестве множителя мы можем использовать сравнимые по некоторому модулю числа (в данном случае они будут эквивалентны), и оба выражения при этом дадут одинаковое значение вычисленного остатка. Теоретическое доказательство этого факта я оставлю вне контекста данной работы. Практически же в этом может убедиться каждый. Это может легко проверить каждый, подставив в указанный алгоритм оба приведенных значения.

То есть,
(327680*1140671485 + 12820163) MOD 16777216
даст такой же результат, что и
(327680*16598013 + 12820163) MOD 16777216.

Касательно того, почему в разных источниках фигурирует два разных числа в качестве множителя, можно предположить, что число 16 598 013 использовалось на старых 32-разрядных системах до версии VB 6.0 включительно (в классическом VBA), а число 1 140 671 485, скорее всего, стало использоваться уже на 64-разрядных системах и в VBA начиная с 7-й версии (VB. NET).    

Но, как уже было показано, практических оснований для использования большего числа в качестве множителя, на первый взгляд нет. Оба указанных множителя дают одинаковый остаток при работе алгоритма, но при этом, логично предположить, что вычисления с числом 1140671485 потребуют больше ресурсов. Ответа на вопрос, почему в Microsoft решили использовать большее число, у меня пока нет.

Итак, мы получили правило вычисления остатка, и, таким образом, можем вычислить всю последовательность. Забегая вперед, нужно отметить, что в Microsoft весьма ответственно подошли к выбору параметров своего алгоритма и при указанных значениях множителя, приращения и модуля длина последовательности будет максимально возможной (16777216 уникальных значений, что соответствует значению модуля).  

Но получение остатка — это т олько половина дела. Само значение, возвращаемое функцией Rnd() вычисляется так:
rnd = x1/m.
Так как x₁ всегда будет меньше m, то, соответственно, 0 ≤ rnd < 1.

В доступной на данный  момент справке от Microsoft без указания каких-либо подробностей говорится, что функция Rnd() возвращает значение типа Single (число с плавающей точкой размером 32 бита), меньшее 1, но большее или равное нулю.

Практические вычисления

Итак, для начала попробуем запустить в редакторе VBA следующий код для вычисления псевдослучайных чисел:

Dim i As Integer

For i = 1 To 3
   
    Debug.Print Rnd

Next
‘Листинг 1

В рамках данной статьи я не буду останавливаться подробно на том, как запускать макросы на языке VBA, и о том, что такое процедуры — информации об этом предостаточно и тот, кто захочет, всегда сможет ее найти без каких-либо проблем. Для краткости скажу только, что редактор cценариев VBA можно открыть в любом офисном приложении, нажав сочетание клавиш Alt+F11.

Дадим краткий комментарий к приведенному выше листингу. Мы объявили целочисленную переменную i, которая является счетчиком цикла, и при помощи цикла For три раза подряд запустили встроенную функцию Rnd(). Здесь нужно добавить, что эту функцию можно вызвать двояким образом, что никак не отразится на ее работе: и написание Rnd(), и написание Rnd эквиваленты. Все зависит от стиля написания кода – если вы хотите, чтобы функции зрительно выделялись в общем потоке, то тогда написание Rnd() будет предпочтительным. Если такой цели не стоит – то Rnd  поможет сократить код.

Но нам не достаточно просто вызвать функцию, нам необходимо увидеть результаты ее работы. И эти результаты мы будем выводить в окно отладки кода Immediate при помощи метода Print класса Debug (не забываем, что VBA — объектно-ориентированный язык). Само это окно вызывается в редакторе VBA при помощи сочетания клавиш Ctrl+G или через опцию Immediate Window в пункте меню View.

Если же мы еще раз запустим указанный код, то данные в окне Immediate будут выглядеть следующим образом:

Как видно, мы получили еще 3 значения результата работы функции Rnd()

Теперь перед нами стоит задача создать эмулятор работы функции, для того, чтобы проверить полученные данные. Не будем далеко ходить и создадим такой эмулятор непосредственно в Excel. Для этого будем вычислять вычисляемые при работе функции Rnd() данные, используя ранее указанные параметры:

x₀ = 327680;
а = 16598013;
с = 12820163;
m = 16777216.

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

=ОСТАТ(16598013*RC[-1]+12820163;16777216).

Само значение Rnd мы вычисляем в другой ячейке по формуле:
=RC[-1]/16777216.

Получим следующие результаты:

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

Еще несколько нюансов

Можно заметить, что при каждом новом запуске функции Rnd мы начинаем вычислять последовательность не с самого начала: в качестве x0 мы будем иметь последний вычисленный остаток. Если мы выполнили 6 итераций , то при последующем запуске функции Rnd функция возьмет в качестве остаток, вычисленный в 6-й итерации, который в данном случае (что видно по результатам работы эмулятора) будет равен 12997982. 

Но что если нам необходимо «сбросить» счетчик и начать все вычисления с самого начала? Для этого в редакторе VBA необходимо нажать на кнопку Reset.

 Итак, запустим код из Листинга 1, нажмем на кнопку Reset и снова запустим наш код. В итоге в окне Immediate получим следующий результат:

То есть, кнопка Reset приводит систему в ее изначальное состояние. И если нам необходимо начать вычисления с «нулевой точки», нужно будет нажать ту самую кнопку.

Теперь следует сказать несколько слов об аргументах функции. До этого мы запускали функцию Rndбез аргументов — вернее, в качестве аргумента мы использовали x0, вшитый в функцию по умолчанию. Здравый смысл подсказывает, что мы можем задавать любое число в качестве x0, достаточно просто указать его в скобках. Но в данном случае, как можно будет скоро убедиться, здравый смысл будет не самым лучшим помощником.

Попробуем ввести любое положительное число в качестве аргумента функции. Запустим следующий код:

Dim i As Integer

For i = 1 To 3
   
    Debug.Print Rnd(333)

Next
‘Листинг 2

Получим в итоге всю ту же самую последовательность:

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

Эхо надмозга

Сколько бит может занимать аргумент функции? Русскоязычная справка от Microsoft, скажем прямо, переведена достаточно криво. Возможно, это делали некие энтузиасты, но это, конечно, их не извиняет, имхо. Весьма вероятно и то, что справку переводили некие переводчики-надмозги (для тех, кто не в курсе данного термина — приглашаю воспользоваться специальным сертифицированным поисковиком (это важно!)), не совсем владеющие терминологией и не совсем разбирающиеся в теме. Прямая цитата гласит:

Необязательный аргументNumber является одним или любым допустимым числовым выражением

Согласитесь, довольно сложная для понимания конструкция. В оригинале эта фраза выглядит так:

The optional Number argument is a Single or any valid numeric expression.

Это означает, что необязательный аргумент Number принадлежит к типу Single, либо может быть любым другим допустимым числовым выражением.

Попытки построить новые последовательности

Тип Singleв VBA — это число с плавающей точкой одинарной точности и для его хранения в памяти выделяется 32 бита (4 байта). Допустимое числовое выражение — это константа или переменная (некое выражение, содержащее в себе константы и/или переменные). Но итоговое значение этого выражения, так или иначе, должно соответствовать типу Single.

Итак, с положительными аргументами функции Rndмы разобрались. Ситуация изменится, если мы введем в качестве аргумента число 0.

Dim i As Integer

For i = 1 To 3
   
    Debug.Print Rnd(0)

Next
‘Листинг 3

Выполним код Листинга 3 и получим следующий результат (при этом не забудем предварительно нажать на Reset):

Как видим, число 0 в качестве аргумента всегда будет выдавать одно и то же число в любой итерации работы функции. Для полноты картины следует сказать, что любое отрицательное число будет вести себя так же. Введем в качестве аргумента -1 и получим следующее:

Итак, казалось бы, если не положительное, то хотя бы число n ≤ 0 можно использовать в качестве x0, отличного от заданного по умолчанию. На самом деле, это утверждение, если и соответствует истине, то не более, чем на половину.

Для проверки данной гипотезы используем эмулятор работы функции Rnd. Введем туда 0 в качестве x0 и получим следующее: 

Как видно, если в эмуляторе в качестве x₀ взять 0 в первой (или нулевой – кому как больше нравится) итерации, то полученное значение rnd будет отличаться от того, которое возвращает нам функция (а именно: 1,953125*10^-2).  

Аналогичную картину мы получим и для числа -1:

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

Логика была такая: для отрицательных чисел правила модульной арифметики не такие очевидные, как это может показаться. Например, по этим правилам:
-1 ≡  9 (mod 10).

Это становится понятно, если мы представим любое число q, дающее при делении на m некоторый остаток r как:

q = m∙t + r.

То есть, 9 мы можем представить как 10∙0 + 9, 19 – как 10∙1 + 9. Таким образом -1 представляется как: 10∙(-1) + 9.

Некоторые языки, насколько я знаю, могут игнорировать эти правила. Например, C++ в качестве результата операции вычисления остатка от деления -1 на 10 (-1 % 10 в синтаксисе C++), вообще, выдаст -1, а не 9.

Поэтому для исключения всех возможных неожиданностей я решил попробовать взять в качестве x₀ и -1, и 1. Вдруг, VBA высчитывает остаток наподобие C++, а потом, например, берет в качестве x₀ его абсолютное значение. 

Опережая события, скажу, что задав аргумент n ≤ 0 для функции Rnd(), VBA будет оперировать двумя значениями x₀. Первое из этих значений — мнимое, тот самый аргумент, который мы ввели в скобках. Второе — реальное, то есть то значение, с которым работает функция для вычисления возвращаемого ей значения и которое до настоящего момента пока что скрыто от нас.

Но с числом 0 все обстоит немного по-другому. Мы уже видели, что 0 может использоваться в качестве мнимого x₀. Но при использовании нуля в качестве аргумента для Rnd() есть еще один момент. Попробуем выполнить следующий код:

Dim i As Integer

For i = 1 To 3
   
    Debug.Print Rnd()

Next

For i = 1 To 3
   
    Debug.Print Rnd(0)

Next
‘Листинг 4

Получим следующий результат:

Мы видим, что первые три значения полученной последовательности соответствуют «стандартному» алгоритму, в котором x₀ равен 327680. Далее мы видим, что расчет останавливается на последнем полученном значении (x₂) и возвращаемое функцией значение соответствует именно этому значению (в данном случае — реальному числу 8949370, т. е. остатку, вычисленному на первой итерации, считая, что функция начинает работу на нулевой итерации). 

Если мы захотим вновь «стронуть с места» вычисления, то для этого достаточно будет снова использовать функцию Rnd() без аргумента (либо с положительным аргументом). В данном случае вычисления начнутся с x₂₍₀₎ = 8949370.  

Легким движением руки…

Как уже было сказано, результатом работы функции Rnd() является псевдослучайное число типа Single. Но в VBA есть и такой тип чисел с плавающей точкой, как Double, который выделяет для числа 64 бита.

Казалось бы, если мы захотим «превратить» число типа Single в число типа Double – то мы вряд ли сможем получить при этом какие-то новые значащие биты. Не будем вдаваться в тонкости машинного представления чисел. Говоря образно, при таком переводе числа из одного типа в другой, не стоит ожидать чего-то иного, помимо добавления нулей в добавленные младшие/старшие 32 разряда.

То есть, если предположить, что у нас есть число, под которое выделено 2 десятичных разряда (например, 0.1), то добавив еще два десятичных разряда в представление числа, мы не можем рассчитывать получить что-либо, помимо 0.100, 000.1 или 00.10. Но, как оказывается, при работе функции Rnd это правило не работает. Попробуем объявить переменную типа Double и записать в нее результат работы алгоритма.

Dim a As Double

Dim i As Integer

For i = 1 To 3

    a = Rnd
    
    Debug.Print a

Next  
‘Листинг 6

И, кто бы мог подумать! Мы получаем те самые значащие биты:

Для исключения варианта погрешностей, искажений при переводе из одного типа числа в другой, повторим эту же операцию в эмуляторе (предварительно установив числовой формат данных ячейки и число знаков после запятой, равное 15). В итоге получим результаты совершенно идентичные вышеприведенным:

Как такое возможно? Мое предположение такое: изначально приложение получает результат в формате Double и уже только после этого переводит его в Single. Сказать что-то более конкретное по этому поводу я пока что не могу. Вполне возможно, что кто-то из читателей знает об этом больше. Если это так, то мне весьма хотелось бы, чтобы знающий человек озвучил эту информацию в комментариях. 

Подводя итоги

Итак, образно говоря, данную статью можно рассматривать как своеобразный КМБ по теме генерации псевдослучайных чисел как в частном (VBA), так и в общем случае. Мы кратко разобрали, что такое линейный конгруэнтный алгоритм, немного затронули терминологию, а также прошлись по азам модульной арифметики. Говоря непосредственно о VBA, мы рассмотрели некоторые нюансы работы функции Rnd(). 

В следующих материалах (но это будет не очень скоро, как оказалось в процессе работы) я планирую рассказать о работе оператора Randomize, который, как говорится, в официальной справке, инициализирует настоящий генератор случайных чисел! Хотелось бы отметить, что в справке по функции Rnd написано, что данная функция  во время своей работы возвращает именно псевдослучайное число.

Также я планирую рассмотреть принципы работы того, что можно назвать хеш-функциями (скажу сразу — что эти хеш‑функции вполне справедливо можно назвать псевдохеш-функциями), которые переводят мнимое начальное значение аргумента функции в ее реальное начальное значение, которое используется в VBA для вычисления последовательности псевдослучайных чисел. Вероятнее всего, это снова будет формат лонгрида. Материала накопилось достаточно.

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

На этом пока все. Надеюсь на конструктивный фидбек. До новых встреч на Хабре!