Часть 1

Самоучитель VBA. Код, задающий массив переменной длины, куда записываются данные работы функции Rnd(). В оригинале - результаты броска монеты. 0 - орел, 1 - решка. Если целая часть выражения 2*Rnd() равна 0 - значит выпал орел, если больше 1 - выпала решка. При выпадении трех орлов (или решек) подряд, код прекращает работу. Но на каких принципах работает функция Rnd()? Вот именно из этого вопроса и возникло настоящее исследование.

В прошлой серии

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

Сама формула алгоритма от Microsoft выглядит так:
x₁ = (327680 *16598013 + 12820163) MOD 16777216, где
327680 – x₀;
16598013 – множитель (multiplier (a));
12820163 – приращение (increment (c));
16777216 – модуль или делитель (modulus (m));
MOD – операция вычисления остатка (при целочисленном делении).

Значение, возвращаемое функцией Rnd() вычисляется как: rnd = x₁/16777216. Поскольку 0 ≤ x₁< 16777216, то значение rnd будет лежать в интервале от 0 до 1 (1 в интервал не включается). Понятно, что функция для вычисления значения x₁ в следующей итерации, будет брать в качестве x₀ значение остатка ( x₁), вычисленное в предыдущей итерации. Таким образом, можно сделать вывод, что ЛКМ - это функция рекурсивная .

Также необходимо сказать, что вероятнее всего в настоящее время в качестве множителя берется число 1140671485. Но оба числа - и 16598013, и 1140671485 - сравнимы по модулю с делителем (числом 16777216), поэтому по правилам модульной арифметики не имеет значения, какое из этих двух чисел использовать (подробнее об этом - в первой части). Для расчета результата работы функции я взял число 16598013 в целях сделать вычисления менее громоздкими.

Длина последовательности

В первой части материала уже было сказано, что длина последовательности, вычисленной при помощи функции Rnd() будет равна числу 16777216 (модулю). То есть, в данном случае мы получим последовательность, состоящую из 16777216 уникальных чисел, после чего алгоритм перейдет на новый виток и повторит всю последовательность заново. Следует уточнить, что для любого целого x₀ длина последовательности окажется неизменной – все те же 16777216 чисел.

В первой части эту информацию мы просто приняли к сведению, но возможно ли ее проверить? Понятно, что при помощи эмуляции в Excel сделать это будет весьма затруднительно (эмуляция функции Rnd() описана в первой части), поскольку нам придется иметь дело с 16777216 значениями остатка, а следовательно - как минимум, с таким же количеством ячеек. Понятно, что выполнять такую работу в Excel вряд ли было бы разумным решением.

Что же, вероятно придется действовать непосредственно при помощи средств языка VBA. Итак, приступим…

В первой части мы уже выяснили, что можно записывать значение, возвращаемое функцией Rnd(), в переменную типа Double, что даст нам точность в 15 десятичных знаков после запятой. Этой точности вполне хватит для того, чтобы вычислить необходимое нам значение остатка (он же x₁).

Итак, x₁ = rnd*16777216. Идея простая: нам достаточно вычислять x₁ для текущей итерации алгоритма и при этом знать ее номер. x₁для первой итерации будем считать эталонным значением, и каждый раз сравнивать его с x₁, полученным в текущей итерации. Как только эталонный x₁ станет равным текущему x₁, мы поймем, что алгоритм «зашел» на новый виток. Номер итерации, соответственно, даст нам длину последовательности. Ну что же, поехали!

Dim a As Long: Dim inc As Long: Dim modulo As Long: Dim j As Long
Dim stand As Double: Dim y As Double: Dim random As Double: Dim x1 As Double

a = 16598013
inc = 12820163
modulo = 16777216

j = 0 ’Считаем начальную итерацию нулевой 
random = Rnd()
stand = random * modulo

Do

    j = j + 1
    random = Rnd()
    x1 = random * modulo
    
Loop Until stand = x1 

MsgBox (j)
‘Листинг 1

В данном примере использован цикл с постусловием, поэтому для получения верного значения длины последовательности будем считать начальную итерацию нулевой (что должны весьма одобрить it-специалисты). Это понятно, поскольку при выполнении кода Листинга 1 мы получим одну «лишнюю» итерацию.

В итоге получим «нужное» нам сообщение:

Вот она - длина изучаемой последовательности!

Ищем реальное х0

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

Напомню: если мы берем в качестве аргумента функции число 0, то на выходе мы получим следующий результат (в примере мы «заставили» функцию сделать 3 итерации):

При этом эмулятор при подстановке в ЛКМ 0 в качестве x₀ выдавал следующее:

Я предположил, что возвращаемое функцией при вводе аргумента n ≤ 0 число - это самая первая ее итерация. Как видно, если мы введем в эмулятор число 0, в самой верхней строке мы получим совершенно другое число.

При этом можно предположить, что 0, в этом случае является мнимым x₀, в то время как реальное x₀ остается скрытым для нас. Можно ли найти его каким-либо образом?

На самом деле, в общем случае вопрос так и остался бы открытым. Можно предположить, что выражение Rnd(0) запустит ЛКМ с параметрами, отличными от установленных по умолчанию параметров функции Rnd(). В этом случае мы не можем говорить о том, что функция имеет дело с реальным или мнимым x₀. Если у нас есть ЛКМ с совершенно другими параметрами (множителем, приращением, модулем), то, соответственно, 0 даст значение rnd отличное от того значения, которое даcт 0 в ЛКМ со стандартными параметрами.

С другой стороны, если предположить, что параметры остаются теми же, мы всегда можем найти остаток (x₁), которым оперирует алгоритм для вычисления значения rnd. И, как станет видно, здесь Microsoft не подготовила для нас никаких подвохов.

Итак, мы имеем значение rnd, равное 0,001953125. При вычислении длины последовательности мы уже искали значение остатка, хотя и не выводили это значение на экран. В нашем случае:
x₁ = 0,01953125*16777216 = 327680

А вот это уже интересно! Если предположить, что параметры алгоритма не поменялись, то Rnd(0) подставляет в алгоритм число, которое дает остаток, равный 327680. Напомню, что 327680 – это x₀ для начальной итерации стандартного ЛКМ в VBA. То есть, здесь разработчики подобрали такое число, которое дает «минус первую» итерацию работы стандартного алгоритма. Для большего понимания стоит привести результаты работы эмулятора:

Здесь видно, что остаток, вычисленный в предыдущей итерации, действительно, используется в качестве начального значения (x₀) для текущей итерации алгоритма.

Для большей наглядности: исследуя изображение выше, становится понятно, что во второй итерации в качестве x₀ используется число 8949370. В этой операции вычисляется остаток (x₁), равный 9722709. Этот остаток используется в качестве x₀ уже в третьей итерации. Само же число 8949370 вычисляется в первой итерации.

Итак, чтобы узнать, какое число «порождает» x₀, используемое в третьей итерации, нам нужно найти значение x₁, вычисленное в первой итерации. Соответственно, для того, чтобы узнать, какое число даст остаток 327680, нам нужно узнать остаток, вычисленный в итерации с номером -2. Если последовательность циклична и содержит 16277216 чисел, то итерация с номером -2 будет соответствовать итерации с номером 16277214 (учитывая то, что последовательность будет оканчиваться на итерации №16277215, а начинаться – с №0).

Теперь в теории мы можем легко вычислить любое x₀, зная x₁ и номер итерации, в которой вычисляется это x₁. Но это только в теории. Нужно сказать, что в данном случае мы узнали нужный нам номер итерации только благодаря «подсказке» разработчиков. Например, Rnd(-1) даст следующий результат:

Это значение соответствуют значению x₁, равному 3758214. Естественно, в данном случае, мы не можем сказать ничего определенного о номере итерации, в которой было получено указанное значение.

ЛКМ тем и хорош, что мы легко можем спуститься вниз, зная значение либо x₀, либо x₁ (либо оба из них), но в то же время, задача «подъема» наверх уже будет не такой тривиальной.

Тяжелый подъем

Всем известно, что круглое легче катать, чем носить. Также и с движением по вертикали: спускаться вниз можно без особых проблем, а вот подниматься на Эверест весьма и весьма непросто, особенно если его высота составляет 16777216 итераций. Впрочем, настоящий исследователь никогда не ищет легких путей. Если надо подниматься в гору, значит, нужно подниматься, хотя народная мудрость и говорит, что это – не самое умное занятие.

Итак, наша задача – найти такой x₀, который даст нужное нам x₁. Что нам известно? Остаток (x₁). Как известно, любое число q, дающее остаток r при делении на модуль m можно представить как:
q = m∙t + r, где
t – частное от деления q на m.

Напомню, что в рамках ЛКМ x₁ высчитывается как:
x₁ = (x₀∙a + c) MOD m.

В рамках нашей задачи мы понимаем, что x₁ = r, а число q = x₀∙a + c.

Это значит, что
q = x₀∙a + c = m∙t + x₁.

То есть:
x₀∙a + c = m∙t + x_{1 (1)}.

В итоге мы имеем уравнение с двумя неизвестными – x₀и t, где основное неизвестное, которое нам требуется найти – x₀. В общем случае это уравнение будет иметь бесконечное число пар решений. Но у нас есть одна важная зацепка: и t, и x₀должны быть целыми числами.

Надеюсь то, почему частное t должно быть целым, понятно. Но на всякий случай: речь идет о целочисленном делении и о вычислении целого остатка. То есть, мы одно целое число делим на другое целое число и получаем некоторый целый остаток. Если q – целое число, m – целое, то частное от деления q на m также должно быть целым в том случае, если мы ищем остаток. Также целым должно быть и число x₀: поскольку q = x₀∙a + c – целое число, a и c – целые числа, то и x₀ также должно быть целым.

Итак, выразим из получившегося уравнения 1 x₀:
x₀ = (m∙t + x₁- c)/a.

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

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

Но так как мы решаем практическую задачу, то t у нас будет одно, и причем положительное, которое даст нам одно целое положительное x₀, меньшее 16777216. Соответственно, и количество «претендентов» у нас сокращается. Мы будем выбирать из 16777216 целых значений t от 0 до 16777215 включительно.

Это становится понятно, если еще раз взглянуть на уравнение:
q = m∙t + x₁.

Так как 0 ≤ x₁ < q, то m∙t ≤ q. Понятно, что при таком раскладе, учитывая, что m > 0, и к тому же является целым числом, t никак не может превышать значение m.

В итоге, самое большее, что нам нужно будет сделать - перебрать 16777216 чисел среди которых обязательно должно быть такое, которое даст подходящее нам x₀.

В первый момент, не осознав весь масштаб задачи, я решил было осуществить поиск x₀ через стандартные средства Excel, без использования VBA. Сказано – сделано! Быстро забиваем в Excel формулу ЛКМ от Microsoft и начинаем подбирать x₀. В итоге получаем примерно следующее:

Самонадеянная попытка "быстро" найти нужное число

Понятно, что искать x₀ подобным образом – затея несколько неразумная. Насколько я знаю, Excel содержит 65536 строк, думаю, что столько же и столбцов. Не факт, что при этом мы смогли бы найти нужное значение в рамках одного рабочего листа – ведь никто не гарантирует, что нужное значение попадется всего лишь на первой сотне тысяч значений. Отнюдь!

Зато в этот момент можно ощутить себя криптографом 50-х годов прошлого века – ведь ЛКМ, если верить Вики, был впервые предложен 1949 году. Хотя и это ощущение будет обманчивым – скорее всего, расчеты мы осуществляли бы при помощи арифмометра, либо, в лучшем случае, на ламповых многотонных устройствах. Excel на тот момент был несбыточной фантастикой! Соответственно, на подобный поиск, который в худшем случае мог бы занять у нас пару-тройку дней, в те времена запросто могли уйти месяцы или даже годы.

Старый добрый брутфорс

Не могу с точностью сказать, к счастью или нет, но мы живем не в 50-х годах прошлого века. И у каждого из нас есть огромное количество вычислительной мощности. И как это часто бывает – если есть мощность, значит, мы можем прошибать стену не лбом, и даже не лбом в каске, а мощным и массированным таранным ударом.

Брутфорс – как много в этом звуке для сердца хакера слилось! Этот метод постепенно отходит в прошлое, хотя, вероятно, на долгое время останется актуальным для решения узких и специфических задач. Итак, применим этот метод и в нашем случае – устроим перебор чисел t для поиска нужного нам x₀.

Но как, вообще, узнать, что число целое? По идее – отбросить целую часть и рассмотреть часть дробную. Если дробная часть равна 0 (или пренебрежимо мала), мы можем считать такое число целым. Также и наоборот – если дробная часть стремится к 1, мы также будем считать такое число целым. Итак, поехали!

Dim a As Double: Dim inc As Double: Dim modulo As Double:
Dim x0 As Double: Dim t As Double

a = 16598013
inc = 12820163
modulo = 16777216
resid = 327680 ‘Это наш остаток (x1)

For t = 0 To 17000000 ‘Округлим до большего количество перебираемых 
  ‘чисел – чтобы лишний раз не возиться с вводом больших чисел.

    x0 = (t * modulo + resid - inc) / a
    x0 = Abs(x0 - Fix(x0))
    
    If x0 < 0.00000001 Or x0 > 0.999999999 Then
    
        MsgBox (t)
                    
    End If

Next
‘Листинг 2

Несколько пояснений: думаю, функция Abs() не вызовет ни у кого вопросов – она возвращает абсолютное значение числа. Fix() – функция, возвращающая целую часть дробного числа. В принципе, понятно, что иногда (хотя и очень редко), мы будем получать отрицательное значение x₀ (хотя по условию задачи мы можем, вообще не рассматривать отрицательное x₀) и, соответственно, в данном случае мы будем получать отрицательное значение дробной части числа. Чтобы исключить подобные случаи мы и будем использовать функцию Abs().

Можно сделать так, чтобы вместо значения t программа выдала бы сразу значение x₀(тем более, что в коде это значение вычисляется напрямую). Но для большей наглядности я сделал так, чтобы программа выдавала значение именно частного. Для большего удобства можно также «запилить» ручной ввод остатка в форму при запуске макроса, а не исправлять его значение каждый раз в теле программы, но это уже мелочи. Главное, что при запуске макроса спустя какие-то доли секунды мы получаем то самое заветное число!

Немедленно забиваем его в ячейку Excel и видим следующее:

Целое значение x₀!!! Не теряя ни секунды, забиваем его в эмулятор и видим:

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

Подводя итог, мы выяснили, что функция Rnd() при аргументе, равном 0, оперирует двумя значениями x₀ – реальным и мнимым. В данном случае мнимое значение равно 0, реальное же – 7796289. По какому принципу выбирается это значение? В данном случае просто – это минус-первая итерация по отношению к стандартной нулевой итерации, где x₀ равен 327680.

Небольшой UPD

Уже после того, как я написал Листинг 2, и соответственно, сделал теоретическое обоснование для него, приведенное в предыдущем разделе, я понял, что поиск нужного x₀ можно было сделать гораздо проще без всех этих поисков t и, соответственно, всей вышеприведенной головоломки. Мы могли просто запустить стандартный ЛКМ и искать в каждой операции x₁, сравнивая его с эталонным значением. При этом мы запоминали бы x₁, найденный в предыдущей итерации.Когда x₁ текущей итерации станет равным эталонному, то x₁ из предыдущей итерации будет тем самым искомым значением реального x₀.

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

Вперед к новым вершинам

Итак, мы смогли решить задачу поиска x₀ при заданном значении остатка, вычисляемом в ходе работы ЛКМ. Теперь можно попробовать составить таблицу соответствия мнимых и реальных значений x₀, которыми фигурирует функция Rnd() в VBA. Для этого создадим вспомогательный макрос, который будет захватывать числовое значение из ячейки Excel и будет использовать его в качестве аргумента функции Rnd():

Dim a As Double: Dim inc As Double: Dim modulo As Double:
Dim x0 As Double: Dim y As Double: Dim j As Long: Dim round As Double

a = 16598013
inc = 12820163
modulo = 16777216

j = CLng(ActiveCell.Value)
round = Rnd(j): resid = round * modulo

ActiveCell.Offset(0, 2).Value = resid
ActiveCell.Offset(0, 3).Value = round 	
‘Листинг 3

В понравившуюся нам ячейку вводим числовое значение аргумента функции. Выделяем ее и запускаем макрос из Листинга 3. Программа приводит значение в выделенной ячейке к числовому типу Long, после чего вычисляет значение x₁ и записывает его в другую ячейку рабочего листа Excel. Параллельно с этим мы записываем в новую ячейку и само значение rnd, выдаваемое функцией. Полученное значение x₁ вводим в макрос из Листинга 2 (при желании можно все это объединить в один макрос). Вычисляем реальное x₀, после чего еще переводим это значение в 16-ричную систему. В итоге получим:

На тот момент, когда я получил это значение, у меня еще не было понимания, почему в Microsoft выбрали значение 8000BF₁₆ в качестве реального значения x₀ при мнимом x₀, равном -1. Единственное, что я смог тогда утверждать: это число не соответствует минус-второй итерации стандартного алгоритма, ведь этот вариант может показаться логичным, учитывая то, что аргумент 0 соответствует минус-первой итерации работы стандартного ЛКМ. Но, если бы это было так, то x₁ при значении аргумента -1, должно было бы быть равно 7796289, но, как видно, полученное x₁ у нас совсем другое.

О том, почему в качестве реального x₀ для аргумента -1 используется число 8388799, я планирую рассказать уже в следующей части.

Что же, идем дальше, и получаем следующую картину:

Таблица соответствия мнимых и реальных x0

Отсюда видно, что -1 можно представить как -(2⁰), и тогда становится ясно, что 8000BF₁₆ – это просто реальное x0 для -(2²), откуда вычли единицу. Но на самом деле все наоборот, это к реальному x₀ для мнимого, равного -(2⁰), прибавляется единица. О том, почему в качестве реального x₀ для аргумента -1 используется именно число 8388799, я планирую рассказать уже в следующей части.

Здесь уже можно выявить закономерность, которая будет соблюдаться и далее вплоть до самого последнего отрицательного целого числа, которое cможет воспринять VBA. Итак, мнимому значению -2 соответствует реальное значение 192 (C0₁₆). Мнимому значению -8 – реальное 193 (C1₁₆). Тут явно прослеживается следующая закономерность: реальные числа x₀, соответствующие нечетной степени 2 (вернее, модуль которой соответствует этой степени), будут отличаться друг от друга на 1.

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

Таблица соответствия нечетных степеней двойки.

Последнее число с нечетной степенью, которое сможет обработать VBA – это -2¹²⁷, которому будет соответствовать реальное x₀, равное 255 (FF₁₆).

А что можно сказать о числах с четной степенью 2? Значения их реальных x₀ также будут отличаться друг от друга на единицу:

Таблица соответствия нечетных степеней двойки.

Теоретически данная последовательность при мнимом x₀, равном -2¹²⁸, даст реальное x₀ 8000FF₁₆. На практике же такое число вызовет переполнение и последним числом, с которым практически сможет работать VBA является число:
-2¹²⁷ - 2¹²⁶ - … - 2¹⁰⁵ - 2¹⁰⁴.

Введение в стандарт IEEE-754

Почему именно число -2¹²⁷ - 2¹²⁶ - … - 2¹⁰⁵ - 2¹⁰⁴? Потому что оно является самым малым числом, которое можно представить в 32-битном представлении, используя стандарт IEEE-754. На сегодняшний день представление чисел с плавающей точкой в большинстве своем основывается именно на этом документе. Если говорить коротко, то в 16-ричном представлении это число будет выглядеть следующим образом (FF7FFFFF₁₆):

Представление числа FF7FFFFF16 в двоичном виде — Представление числа FF7FFFFF₁₆ в двоичном виде

Первый разряд, равный единице говорит нам, что число – отрицательное. Следующие 11 разрядов, находящиеся в лиловом блоке, указывают на экспоненту. В десятичном представлении значение лилового блока равняется 254. Далее из этого числа нам нужно отнять 127 и получить реальное значение экспоненты, равное, соответственно 127. Разряды в светло-зеленом блоке представляют мантиссу числа.

Соответственно, первый разряд зеленого блока соответствует числу 2¹²⁶ (идет сдвиг на один разряд – из 127 вычитается 1, и получаем степень двойки, соответствующая данному разряду). Аналогично найдем число, соответствующее последнему разряду – это 2¹⁰⁴. А где же число 2¹²⁷? Числу 2¹²⁷ соответствует экспонента – оно здесь присутствует, но только в неявном виде. В итоге у нас получается уже указанная сумма отрицательных чисел:
-2¹²⁷ - 2¹²⁶ - … - 2¹⁰⁵ - 2¹⁰⁴.

На практике эта сумма будет соответствовать числу -340282346638528859811704183484516925440, но ввести его непосредственно в качестве аргумента у нас не получится: в редакторе VBA оно будет выглядеть как -3.40282346638529E+38. Как видно, последний значащий разряд в этом представлении является результатом округления.

Немного не так будет себя вести Excel – если мы попробуем ввести в ячейку полученное нами число, и выбрать числовой формат этой ячейки, то программа автоматически отбросит у него 24 младших разряда, и представит его в виде: -340282346638528000000000000000000000000,00.

Таким образом, мы видим разницу подходов в представлении чисел в VBA и Excel. В VBA число округляется, а в Excel – отбрасываются "лишние" разряды.

Здесь напрямую можно наблюдать особенность представления чисел в формате IEEE-754. Используя этот формат, мы не можем прибавить к числу 2¹²⁷единицу, и даже 2¹⁰³– при экспоненте, равной 127 все эти числа будут эквивалентны 0 (естественно, в формате 32-битного представления). Первым числом, которое сможет воспринять машина, при данной экспоненте, станет число 2¹⁰⁴. Впрочем, несмотря на то, что абсолютном значении число 2¹⁰³ можно назвать огромным, и даже астрономическим, в относительном значении мы получаем довольно хорошую точность, равную 2^-24 или примерно 0,000006%. Вот эти 0,000006% и есть так называемая одинарная точность,и именно поэтому тип чисел, имеющий 32-битное представление и называется Single.

Далее может последовать вопрос, почему именно данное число является максимальным, ведь мы можем заполнить блок экспоненты единицами и получить, таким образом, экспоненту, равную 128. На самом деле, это можно сделать, и, например, если мы заполним единицами блок экспоненты, а блок мантиссы оставим незаполненным (FF800000₁₆), то на выходе получим значение -∞.

Вот так выглядит минус бесконечность в двоичном виде.

Соответственно, по логике, мы не можем получить число, меньшее -∞. Поэтому если далее мы начнем заполнять мантиссу единицами, на выходе мы будем получать значение NaN (Not a Number).

И, возможно, последний вопрос, который может возникнуть: почему мы имеем дело с 32-битным представлением чисел, ведь мы также можем использовать стандарт IEEE-754 и в 64-битном, и даже в 128-битном представлении? На самом деле, вразумительного ответа на него нет. Вероятно, на тот момент, когда в Microsoft разрабатывали функцию Rnd() (возможно и VBA), 64-битных систем еще не было. А после того как они появились, никто не позаботился переделывать уже работающую систему.

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

Впрочем, 64-битное представление чисел все-таки внесло свою лепту в VBA Excel, но об этом я планирую рассказать в следующих сериях. Не пропустите!

Небольшой UPD №2

Как оказалось, эхо 64-битного представления чисел достигло этого исследования гораздо раньше следующей серии. Как мне удалось выявить опытным путем, самым большим числом, которое VBA воспринимает в качестве аргумента функции Rnd(), является число:
3.40282356779733E+38. Число 3.40282356779734E+38,соответственно, уже даст ошибку переполнения. Но если мы вводим число, большее самого большого числа, которое можно представить в 32-битном виде, значит, мы имеем дело уже с 64-битными числами!

Полученное значение несколько больше числа 3.40282346638528E+38, которое приблизительно равно 2¹²⁷ + 2¹²⁶ + … + 2¹⁰⁵ + 2¹⁰⁴. А как в стандарте IEEE-754 будет выглядеть самое большое 64-битное число, экспонента которого будет равна 127? Не вдаваясь в подробности, оно будет выглядеть как 47EFFFFFFFFFFFFF₁₆ или:

Число 47EFFFFFFFFFFFFF16 в двоичном виде — Число 47EFFFFFFFFFFFFF₁₆ в двоичном виде

Это представление будет соответствовать числу 2¹²⁷ + 2¹²⁶ + … + 2⁷⁶ + 2⁷⁵, которое в виде числа с плавающей точкой будет выглядеть как 3.40282366920938E+38. При этом видно, что число 2⁷⁴ уже будет слишком малым для отображения в 64-битной точности при экспоненте, равной 127.

И здесь мы видим, что точность округления чисел возрастает по сравнению с 32-битным представлением, и будет уже равняться 2^-54 или ≈ 5,55∙10^-17, что соответствует 5,55∙10^-15%. Данная точность уже будет называться двойной, а число, соответствующее ему, будет иметь тип Double.

Итак, у нас есть три числа (в порядке возрастания):
3.40282346638528E+38;
3.40282356779733E+38;
3.40282366920938E+38.

Теперь попробуем вычесть из третьего числа второе, а из второго - первое. Получим следующее (для наглядности я убрал десятичные точки у мантисс числа):

В итоге видно, что самое большое число, воспринимаемое интерпретатором VBA, находится ровно посередине между самым большим числом в 32-битном представлении, и его "аналогом" в 64-битном представлении. И если разность числа 3 и числа 1 равна 2¹⁰³ + 2¹⁰² + ... + 2⁷⁶ + 2⁷⁵, то, соответственно, число, находящееся посередине между ними будет равно:
2¹²⁷ + 2¹²⁶ + … + 2¹⁰⁵ + 2¹⁰⁴+ 2¹⁰²+ ... + 2⁷⁵ + 2⁷⁴ = Число 1 + (Число 3 - Число 1)/2

Поскольку последний член полученной суммы равен 2⁷⁴, а это число, как уже было выяснено, VBA (и любая другая вычислительная система, работающая в 64-формате формате IEEE-754) не сможет отобразить при значении экспоненты, равной 127, необходимо прибегнуть к операции округления. По правилам двоичного округления, отбрасываемый разряд переносится влево, значит, мы должны перенести 2⁷⁴влево, и получить в итоге:
2¹²⁷ + 2¹²⁶ + … + 2¹⁰⁴ + 2¹⁰³, что соответствует 64-битному 47EFFFFFF0000000₁₆. В "плавающем" представлении это число даст следующее:
3.40282356779733E+38.

Все сходится! Полученное значение:

абсолютно идентично полученному опытным путем числу 2;
может быть представлено только в 64-битном виде.

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

Абсолютно идентичная картина будет и для отрицательных чисел – модуль самого малого воспринимаемого VBA числа будет вести себя аналогично.

Что дальше?

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

То есть, если мнимые x₀ равны -3 и -2, то разность между значениями реальными значениями x0 будет равна:
4194496 – 192 = 4194304 (2²²).

Такая же разность будет для реальных x₀, соответствующих мнимым -4 и -3.

Далее видно, что разность между значениями уменьшается в два раза и уже равна 2097152 (2²¹). Затем мы доходим до мнимого значения, равному -8 – а это уже нечетная степень 2. Соответственно, для этого числа мы получаем реальное значение x₀, прибавив единицу к модулю реального x₀ для предыдущего значения нечетной степени двойки (в данном случае – 192 + 1 = 193).

Разность между значениями снова уменьшается в два раза и уже составляет 1048576 (2²⁰). Далее мы доходим до -16 – четной степени двойки и снова уменьшаем разность в 2 раза – до 524288 (2¹⁹).

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

Таким образом мы спокойно добираемся до числа -131070, после которого начинаются некоторые нюансы. Итак, реальное значение x₀ для -131070 равно 16777159 (FFFFC7₁₆). Разность на этом этапе составляет 128. Следовательно, следующее реальное x₀ для числа -131071 будет равно 16 777 287 (1000047₁₆).

Стоп, но это число уже больше нашего модуля – 16777216 (1000000₁₆)! Соответственно, мы знаем, что:
1000047₁₆ ≡ 47₁₆ (mod 1000000₁₆).

Или же в десятичном представлении:
16 777 287 ≡ 71 (mod 16777216).

Понятно, что сравнимые по одному модулю начальные значения для ЛКМ, дадут один и тот же результат при вычислении остатка (об этом говорится в первой части работы), поэтому мы с легкостью можем заменить число 16 777 287 на число 71.

В окрестностях 2-17, мы впервые получаем x0, большее делителя алгоритма. По правилам модульной арифметики мы можем заменить его на меньшее число, сравнимое с ним по модулю. — В окрестностях 2^-17, мы впервые получаем x₀, большее делителя алгоритма. По правилам модульной арифметики мы можем заменить его на меньшее число, сравнимое с ним по модулю.

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

Первые пересечения

Дойдя до числа -524288 (-2¹⁹) мы столкнемся с новым явлением которое я условно назвал пересечением реальных x₀. Поясню, что это значит.

Как видно, реальное x₀ для мнимого -524289 равно 217. Но, как оказывается, число -2⁵¹ также даст реальное x₀, равное 217.

Далее, мы переходим к окрестностям числа -2097152 (-2²¹). Число -2097151 в соответствии со всеми указанными ранее правилами модульной арифметики даст x₀ равное 193.

Но как уже было показано выше, x₀, равный 193, соответствует мнимому x₀, равному -8. Поэтому если мы, например, будем использовать в качестве аргументов функции числа -8 и -2097151, на выходе мы получим одно и то же значение rnd – 0,702644.

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

Вместо заключения

На самом деле, далее я планировал коротко рассказать о том, как ведет себя функция Rnd() при больших (по модулю) значениях аргумента. Впрочем, никаких особых аномалий до числа -16777216 (-2²⁴) мы не увидим. Все будет стандартно: сокращение разности между реальными значениями x₀ до 1, а также преобразование чисел, больших 2²⁴ в меньшие числа, согласно указанным выше правилам модульной арифметики:

Но здесь меня что-то подтолкнуло проверить, что будет, если «скормить» функции дробный аргумент. На первый взгляд, все было просто: я решил использовать аргумент -0,1. Забиваем его в первую попавшуюся ячейку, выделяем ее и запускаем код, указанный в листинге 3 выше:

Что будет, если взять дробный аргумент функции?

Здесь все понятно – функция округляет аргумент до ближайшего целого значения, и использует это округленное значение в качестве мнимого x₀. Это видно по тому, что x₁ в данном примере равен 327680, а это значение, как мы помним, было получено для мнимого аргумента, равного 0.

Аналогично функция будет вести себя, если мы вобьем в ячейку число -0,9. Понятно, что это число будет округлено до -1, что даст нам x₁, соответствующее -1:

Что же, на этом можно было бы остановиться, но что-то подтолкнуло меня еще раз перезапустить функцию, используя в качестве аргумента не значение из ячейки Excel, а вбив это значение напрямую в код. То есть, вместо строк

j = CLng(ActiveCell.Value)
round = Rnd(j)

мы используем следующее:

round = Rnd(-0.1)

После чего вычислим значение реального значения x₀ и увидим следующую картину:

Как видно, если вбивать значение аргумента напрямую в код, функция будет вести себя абсолютно по-другому. Однозначно не могу сказать, какой из двух вариантов ее поведения является багом, а какой – фичей, но могу сказать определенно, что выяснение того, почему у нас появилось довольно странное, на первый взгляд значение x₀, равное 13421962, оказалось довольно увлекательным занятием с довольно неожиданными результатами.

Заодно это понимание позволило также лучше понять поведение функции при сверхбольших (по модулю) значениях (меньше -2²⁴), а также то, почему для аргумента -1 было выбрано значение реального x₀, равное 8388799 (8000BF₁₆). Обо всем этом я планирую рассказать в третьей части этой работы. Не пропустите!

(Не)случайные числа в VBA Excel Ч. 2