gifts2017

Алгоритм расчета Факториала

Опубликовал Матти Нюкянен (Nykyanen) в раздел Программирование - Практика программирования

Пример оптимизации алгоритма под органичения 1С.

ФакториаL9;л числа n (обозначается n!, произносится эн факториаL9;л) — произведение всех натуральных чисел до n включительно:

Для n = 6, n! = 6! = 1*2*3*4*5*6 = 720.

Казалось бы все просто, да нет. Число символов очень быстро растет и быстро выходит за пределы числа, в 1С длина числа 32 знака.

Конечно же, многие скажут надо работать с символами строки, но тогда получается очень медленно.

Есть компромисс, идея в следующем.

Разбивать строку при вычислении не по символам, а по блокам.

Так как максимальная длина числа 32. И допустим мы хотим найти факториал 999, тогда длина второго множителя может быть равна не более 32 – 3 = 29 знаков.

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

Строку результата разбиваем на блоки максимальной длины, преобразуем к числу, умножаем на текущий параметр. И формируем новую строку.

Алгоритм можно использовать рекурсии (именно он и был использован):

F(x) = x * F(x-1), где F(1) = 1

Ускорение получается на порядок по сравнению с посимвольным расчетом.

Во вложении пример обработки.

Изменения: Проверка была выполнена на платформе 8.2.15.319 (на других результаты могут отличаться)

Опытным путем было обнаружено, что максимальная длина числа составляет 311 цифр. Решение: замена макс длины на 311.

Максимальная вложенность рекурсии 1776. Решение: замена рекурсии на цикл.

Функция число в строку и наоборот работает медленно, дольше всего остального. Решение: было заменено на ТаблицуЗначений где в каждой строке храниться число, а не строка.

Добавлена формула Стирлинга для вычисления порядка факториала.  N! ~ sqrt(2 * PI * n) * (n/e)^n

Теперь 10000! расчитывается за 50 секунд = 2.8е35660.

Скачать файлы

Наименование Файл Версия Размер
Новая обработка (исправлены ошибки и оптимизирована работа алгоритма) 11
.epf 7,33Kb
23.07.12
11
.epf 7,33Kb Скачать
Факториал_aka_Zeratul 9
.epf 7,37Kb
23.07.12
9
.epf 7,37Kb Скачать

См. также

Подписаться Добавить вознаграждение
Комментарии
1. Евгений Мартыненков (JohnyDeath) 18.07.12 08:40
А есть практическое применение? Или это просто "джаст фо фан"?
2. Матти Нюкянен (Nykyanen) 18.07.12 09:29
(1) JohnyDeath,
Для решения нестандартных задач, размышлений и
"джаст фо фан"


Подобный подход можно использовать не только для умножения, но и деления, сложения, вычитания и т.д. и т.п.
3. Михаил Ражиков (tango) 18.07.12 10:27
(0) Так как максимальная длина числа 32.
это как?
Прикрепленные файлы:
4. a exeel (aexeel) 18.07.12 10:47
Задача со школьной олимпиады по информатике 8 класса :)
5. Матти Нюкянен (Nykyanen) 18.07.12 11:12
(3) tango, в конфигураторе больше 32 знаков число не создает.
Справка в конфигураторе
Описание: Числовым типом может быть представлено любое десятичное число. Над данными числового типа определены основные арифметические операции: сложение, вычитание, умножение и деление. Максимально допустимая разрядность числа 38 знаков.

Выбрал меньшее из них дабы точно работало.

Спасибо за идею. Попробую с числами побольше.

(4) aexeel, не кто и не спорит.
6. Виктор Левченко (lvictor58) 18.07.12 12:45
Ну о-ч-ч-ень нужная вещь для оптимизации работы бухов, манагеров и спецов складского учета!
7. Ak A (frc) 18.07.12 13:24
(2) Nykyanen,
ну вот и прикиньте, как для нестандартных задач везде и всюду бедете разбивать на "поблочные вычисления" :)
Плюс поставлю, но это - чистой воды баловство.
8. Mu_meson (KAPACEB.AA) 18.07.12 14:23
Я тоже как-то не проникся идеей...

Если делать преобразование в строку непосредственно перед передачей в строковой реквизит, то эти пляски с бубном ни к чему. В коде приложенной обработки достаточно было написать:
"...
знч_фс = Строка(Факт(Знч_ф));
...
"
и результат ее работы был бы такой же.

Если это делалось с осознанием факта, что можно сделать проще но хотелось сложнее, то... сори, но я все-равно не понимаю зачем :)
9. Матти Нюкянен (Nykyanen) 18.07.12 17:57
(3) tango, опытным путем нашел, что длина числа до 311 знаков работает корректно,
выше нет. При таком раскладе алгоритм ускоряется в 10 раз.

Факториал 1000 = ~ 4.0e2568, что явно больше 311 знаков.
Вот и приходиться использовать строку.
10. Ak A (frc) 18.07.12 18:05
(9) Nykyanen,
а вы её в регистр накопления, а потом суммировать в строку :)
Я так думаю - 100 тсрок позволят вам побить рекорд расчета n! :)
11. Матти Нюкянен (Nykyanen) 18.07.12 18:09
(10) frc, идея хорошая.
Но я бы тогда посмотрел на неё по другому.
Массив из чисел по 311 знаков.
Наверное еще можно будет на порядок скорость поднять.
12. Матти Нюкянен (Nykyanen) 19.07.12 12:49
Появилась еще одна проблема.
Это рекурсия в 1С. Глубина вложенности выше 1776 вылетает с ошибкой.
Пришлось заменить на цикл.
13. Матти Нюкянен (Nykyanen) 23.07.12 13:42
Поправил обработку и статью.