Всем привет!
Начнем с классического варианта алгоритма:
Есть еще вариант алгоритма на рекурсии:
Забегу вперед, и напишу, что расчет 50 000! классическим алгоритмом занял 22 сек. против 1,6 сек реализации на Cи Шарп (смотрите публикацию на Хабр Алгоритмы быстрого вычисления факториала).
Реализация на 1С рекурсии вылетает из 1С даже для 2000! Интересные обсуждения на эту тему есть под публикацией 2014 года Библиотека математических функций 1.1
Я подумал, что в жизни, наверное, нет задач, в которых надо рассчитать факториал единожды. Подумал, что чаще встречаются задачи, в которых факториал считается для некой последовательности чисел или для разных вариаций (сценариев) - по сути несколько раз.
Также подумал, что можно использовать в некотором смысле машинное обучение: если рассчитать факториал для 10 000, запомнить результат, то при расчете факториала для 10 001 не придется заново умножать с 1 ... до 10 001, а воспользуемся формулой 10 000! * 10 001.
Для такой оптимизации я добавил в алгоритмы Соответствие:
Алгоритм Классический + Соответствие стал таким:
Алгоритм Рекурсия + Соответствие стал таким:
Тестовый расчет проводил по нарастающей - сначала для 10 000, затем для 25 000, затем для 50 000. Для классического варианта с учетом "накопленного опыта", то есть с применением Соответствия, результат стал таким - 1 сек, 4 сек, 16 сек.
То есть 50 000! был рассчитан за 16 сек, с учетом того, что до этого был рассчитан факториал для 25 000.
Есть ли в этом доля оптимизации? Наверное, есть, если принять условие, что факториал будет считаться несколько раз для какой-нибудь практической задачи.
Из публикации Алгоритмы быстрого вычисления факториала
был взят алгоритм вычисления деревом и переписан на язык 1С:
Факториал для 50 000 был рассчитан за 14 сек без применения Соответствия. Ускорение ощутимо!
Теперь добавим "машинное обучение" - алгоритм деревом + Соответствие:
Также использовал расчет по нарастающей - сначала для 10 000, затем для 25 000, затем для 50 000. Для расчета деревом с учетом "накопленного опыта", то есть с применением Соответствия, результат стал таким - 1 сек, 3 сек, 9 сек.
Конечно, данный результат не сравним с результатом 0,9 сек на Си Шарп.
Я продолжил тестировать расчет деревом с учетом "накопления опыта": 75 000! за 13 сек, 100 000! за 18 сек, 66 000! за 8 сек, 15 000! за 1 сек, 37 500! за 3 сек., 42 000! - за 1 сек, 80 000! за 4 сек - все последующие вычисления происходят достаточно быстро...
Собственно, это все, что я смог "выжать" из оптимизации алгоритма расчета факториала!
Тесты проводились на платформе 1С:Предприятие 8.3 (8.3.15.1830), на конфигурации "Управление торговлей", редакция 10.3 (10.3.47.2) - хотя конфигурация не имеет значения - файловая база, толстый клиент на обычных формах.
P.S. Из определения факториала следует формула: (N-1)! = N! / N. То есть, зная факториал числа, можно найти факториал предыдущего числа путём деления значения факториала на само число. Отсюда вытекает задача: допустим, мы уже посчитали факториал для 2500 и 3000, спрашивается - как быстрее рассчитать факториал для 2900?
Делением, начиная с 3000!/3000/2999.... или умножением, начиная с 2500!*2501*2502...
Собственно, это все.
Всем добра!