![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Иллюзия оптимальности
Aug. 16th, 2021 04:59 pmПри нынешнем развитии криптографического и прочего дела на Западе регулярно приходится возводить что-нибудь в очень большую степень. Очевидно, что вычислять ХN путем умножения Х на себя N-1 раз очень неэффективно; гораздо логичнее вычислять X2, X4, X8 и т.п. путем возведения в квадрат очередного результата (не забывая все промежуточные результаты), а потом перемножить степени, соответствующие единицам в двоичной записи числа N.
Посмотрим, как это будет работать, если нам нужно вычислить X63. Для этого мы последовательно вычисляем Х в степенях 2, 4, 8, 16, 32, 48, 56, 60, 62, 63. Как-то это медленновато; интуитивно кажется, что если бы можно было ещё и делить, то после степени 32 можно вычислить 64, поделить на Х и получить искомый результат, и хочется найти способ вычислить то же самое без деления, но быстрее, чем за 10 шагов.
Заметим, что 63 = это 7*8 + 7. Тогда одним из вариантов оптимального пути будет 2, 3, 6, 7, 14, 28, 56, 63 (другой вариант, например, 2, 4, 6, 7, 14, 21, 42, 63).
Дональд Кнут предложил алгоритм получения последовательности операций для определения эффективного пути вычисления XN. Для этого мы строим такое дерево:
по следующей системе: начинаем с дерева, состоящего только из корня (1). Далее на каждом шаге из узла с наименьшим номером K, из которого ещё ничего не растёт, отрастают ветви в новые узлы с номерами K+L, где L - номера во всех узлах пути от корня (1) до K, включая собственно К, если узлы с этими номерами ещё не существуют. И так до тех пор, пока не образуется узел с номером N, после чего мы прослеживаем путь от него до вершины и определяем, каким способом выполнять умножения.
Казалось бы, всё довольно алгоритмически эффективно, красиво и оптимально, кратчайший путь по дереву и всё такое, ан поди ж ты.
Для числа 77 алгоритм даёт 2, 3, 5, 7, 14, 19, 38, 76, 77 (9 шагов), а оптимально - 2, 4, 8, 9, 17, 34, 43, 77 (8 шагов).
И вообще, нарисовать одно общее для всех чисел оптимальное дерево невозможно - ломается на 149.
Посмотрим, как это будет работать, если нам нужно вычислить X63. Для этого мы последовательно вычисляем Х в степенях 2, 4, 8, 16, 32, 48, 56, 60, 62, 63. Как-то это медленновато; интуитивно кажется, что если бы можно было ещё и делить, то после степени 32 можно вычислить 64, поделить на Х и получить искомый результат, и хочется найти способ вычислить то же самое без деления, но быстрее, чем за 10 шагов.
Заметим, что 63 = это 7*8 + 7. Тогда одним из вариантов оптимального пути будет 2, 3, 6, 7, 14, 28, 56, 63 (другой вариант, например, 2, 4, 6, 7, 14, 21, 42, 63).
Дональд Кнут предложил алгоритм получения последовательности операций для определения эффективного пути вычисления XN. Для этого мы строим такое дерево:
1
|
2
/ \
3 4
/\ \
/ \ \
5 6_ 8
/ \ \ \ \
/ | \ \ \
/ | \ \ \
7 _10_ 9 12 16_
/ / /\ \ \ \ \ \
/ / / \ \ \ \ \ \
14 11 13 15 20 18 24 17 32
по следующей системе: начинаем с дерева, состоящего только из корня (1). Далее на каждом шаге из узла с наименьшим номером K, из которого ещё ничего не растёт, отрастают ветви в новые узлы с номерами K+L, где L - номера во всех узлах пути от корня (1) до K, включая собственно К, если узлы с этими номерами ещё не существуют. И так до тех пор, пока не образуется узел с номером N, после чего мы прослеживаем путь от него до вершины и определяем, каким способом выполнять умножения.
Казалось бы, всё довольно алгоритмически эффективно, красиво и оптимально, кратчайший путь по дереву и всё такое, ан поди ж ты.
Для числа 77 алгоритм даёт 2, 3, 5, 7, 14, 19, 38, 76, 77 (9 шагов), а оптимально - 2, 4, 8, 9, 17, 34, 43, 77 (8 шагов).
И вообще, нарисовать одно общее для всех чисел оптимальное дерево невозможно - ломается на 149.
