К вопросу о математике

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

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

Пнп: Начиная с этого момента сторонники идеи о том, что программирование в наше время состоит в красивом оформлении веб-страничек, могут прекратить чтение, Вы абсолютно правы, математика Вам не нужна…

Ну не нужно так настаивать на своем, Вы ничуть не хуже нас, и Ваша работа по настоящему важна, я ведь уже согласился, что у нас разные представления о программировании…

Да, Вы совершенно правы, что эти олимпиадники не смогут, при помощи последнего фреймворка, нарисовать семь красных перпендикулярных линий в одну строку кода…

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

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

Первое решение совершенно очевидно — берем одну за другой все 10 кнопок (обозначим их число через н для общности), рассматриваем все возможные номера длинной К из нее и подсчитываем те, которые оканчиваются на нужной кнопке. Полученные цифры суммируем и ответ готов. Общее количество просматриваемых вариантов приближенно выразим, как н*В(К), где В(К) — количество возможных ходов длиной К. На самом деле нужно считать сумму по н позициям, поскольку В(р, К) совершенно очевидно зависит от номера кнопки, но как первая оценка сойдет.

Прежде, чем перейти к поиску В, можно существенно уменьшить количество вариантов, применив (нет, пока не математику) здравый смысл. Поскольку перемещение по кнопкам на зависит от предыстории, мы можем обратить задачу и искать все номера длиной К, начинающиеся из нужной кнопки р. Тогда общее количество вариантов составит В(р, К), что в н раз меньше. Ничего себе, мы только что нашли способ убыстрить поиск решения в 10 раз — круто, посмотрим, сколько осталось.

Нам надо оценить В(р, К), для чего определим, что на каждом ходе у нас есть от 2 до 3 вариантов развития событий. Отсюда следует (вообще то это комбинаторика, но интуитивно понятно), что общее количество вариантов составит от 2**К до 3**К (здесь и далее в качестве К я использую К-1). Мы даже можем улучшить эту оценку переходом к вероятностной модели. Считая наличие пальца в каждой кнопке в данный момент равновероятным (сильное утверждение, скорее всего неправильное, но допустимое при грубых оценках) мы можем рассчитать среднее количество вариантов хода 7*2+2(кнопки 4 и 6)*3=20/9~2.22. Тогда оценка будет 2.22**К, причем мы точно знаем, что минимум 2**К мы имеем. Тогда для К=100 получим оценку снизу 2**100=(2**10)**10>(10**3)**10=10**30.

Если мы будем рассматривать один вариант в наносекунду (а это нелегко даже на мощном настольном ПК), то нам потребуется 10**30/10**9=10**21 секунд. Далее припоминаем замечательную мненонику "π секунд равны нановеку" и требуемое время станет 10**21/3.14*10**9 ~ 3*10**11 веков. Мне кажется, что мало кто из читателей доживет до окончания расчётов по предложенной методике. Экспонента — это ужасно, хуже нее только факториал.

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

Проиллюстрируем сказанное примером, начиная с цифры 1 {1234567890}:
начальный вес {1000000000},
после первого переноса {0000010100} (2 варианта),
после второго переноса {2010001001} (5 вариантов),
после третьего {0102040300} (10 вариантов) и так далее.

Алгоритм простой, его можно реализовать даже руками. Общая оценка времени исполнения — К итераций, на каждой из которых для н весов модифицируем не более, чем н связанных весов, итого н**2*К. Для рассмотренного ранее случая 10*10*100=10**4 — совсем немного.

Осталось только оценить длительность каждой операции — это сложение (фигня вопрос), но не простое сложение (с этого места поподробнее). Мы уже установили нижнюю границу ответа в 2**К, то есть нам точно потребуется не менее, чем К битов для представления результата. Верхняя граница 3**К, для нашего случая 3**100=(3**5)**20<(2**8)*20=2**160, то есть в 160 битов мы гарантированно укладываемся. Можно предположить, что нам хватит 128 битов, поскольку 2.2**100<2**128, но принимать такое утверждение на веру страшновато, поэтому нам потребуется число с минимум 160 битами или с 49 десятичными цифрами, в зависимости от имеющейся у Вас библиотеки чисел повышенной точности.

Пнп: Плавающую точку не предлагать, нам нужен совершенно точный результат.
В принятых допущениях операция сложения будет занимать 160/8=20 байт/4=5 сложений целых длиной 32 бита, что никак на сказывается на порядке времени (он остается линейным по К), но может существенно увеличить реальное время расчётов (в разы).

В любом случае результат просто великолепный — мы превратили задачу из принципиально не решаемой в разумное время во вполне решаемую: если одна элементарная операция сложения выполняется микросекунду (а это нетрудно обеспечить даже на плате Ардуино), то общее время не превзойдет 10**4*20/10**6, менее секунды) и мы обошлись безо всякой математики.

Тем не менее, а если нам нужны бОльшие К — конечно, линейный порядок вычислений — это замечательно, но он может приводить (и приведет) к существенным затратам времени для большИх значений. Оказывается, можно существенно улучшить ожидаемое время работы, следите за руками.

Что мы делаем на каждом шаге вычислений (псевдокод):

новое значение = 0;
для всех значений кнопок1
 для всех значений кнопок2
* если (из кнопки 1 можно попасть в кнопку 2)
*   прибавить текущее значение кнопки 1 к новому значению кнопки 2.
текущее значение = новое значение

Если переписать помеченные звездочками две строки в виде

прибавить к новому значению кнопки2 (текущее значение кнопки1 * возможность перехода)

и организовать хранение возможности перехода в виде матрицы с значениями 0 или 1, то можно усмотреть глубокую аналогию с умножением вектора на матрицу. Тогда получаем на каждом шаге В'=В*М и эти шаги необходимо провести К раз Вр=(...((Во*М)*М)...). Используя основные свойства матричной алгебры, данную формулу можно переписать в виде Вр=Во*М**К. Тогда у нас единственное умножение вектора на матрицу, но эта матрица образована многократным умножением матриц. Умножение матриц занимает время н**3, так что общее время составит К*н**3 и возникает законное недоумения — мы привлекли математику, чтобы ухудшить время вычислений в н раз? Нечего сказать, замечательный результат…

Однако мы не закончили — да, умножение матрицы на матрицу занимает н**3 времени и это не изменить, но мы умножаем не разные матрицы, а одну и ту же на себя, а есть замечательный прием для вычисления целой (это важно) степени числа (и матрицы в том числе), основанный на двоичном представлении показателя степени. К примеру, при возведении в степень 100 вместо 99 умножений можно обойтись только 8. В общем случае нам потребуется не более, чем 2*log2(К), что дает нам существенный выигрыш (в случае К=100 выигрыш составит 1000/10=100 раз) и общее время вычислений составит не более, чем 2*log2(К)*н**3. Однако следует учесть, что операции стали сложнее, и если раньше нам требовалось только сложение длинных чисел, то теперь необходимо умножение не менее длинных чисел. Увеличение времени выполнения элементарной операции сильно зависит от используемой библиотеки, его можно оценить, как log2(K), что приводит к оценке нижней границы К, при которой вариант с умножением матриц будет выгоднее, как точно менее 100.

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