При прохождении курса специализации Algorithms by Stanford university на платформе Coursera столкнулась с практическим заданием: получить произведение двух 64-значных цифр:
3141592653589793238462643383279502884197169399375105820974944592
2718281828459045235360287471352662497757247093699959574966967627
Для реализации был выбран метод быстрого умножения Карацубы.
Если вкратце, то это метод быстрого умножения, который позволяет перемножать два n-значных числа с битовой вычислительной сложностью. С теорией алгоритма можно ознакомиться на https://algorithmica.org/ru/karatsuba
Особенность алгоритма - использование рекурсии.
Первая попытка была реализована на Python, так как IDLE (интегрированная среда для разработки ) доступна всем. Но там существует предел глубины возможной рекурсии.
Когда предел достигнут, возникает исключение RuntimeError, так как по умолчанию рекурсивный стек Python не превышает 1000 кадров. Это ограничение можно изменить, установив лимит системным методом sys.setrecursionlimit(Лимит). Однако этот лимит также нужно бы предварительно рассчитать, ведь метод с лимитом другого порядка
потребляет больше памяти.
Поэтому вторую попытку я реализовала на платформе 1С, используя возможность организации рекурсивного вызова функции. Во встроенном языке не установлено конкретного ограничения количества уровней рекурсивного вызова.
Ограничение носит технологический характер.
Прикрепленная обработка содержит рекурсивную функцию, где обеспечен своевременный выход из рекурсии по определенному условию. Что касается быстродействия самого метода Карацубы, то на практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка сотен двоичных (десятков десятичных) разрядов, на числах меньшей длины алгоритм не даёт существенного преимущества из-за большего, чем в наивном алгоритме, числа требуемых сложений, вычитаний и сдвигов.
Внешняя обработка рассчитана на ввод и отображение на форме 32-значных цифр. Однако выполнить операцию с 64-значных цифрами вполне возможно, указывая исходные данные непосредственно в коде и получая промежуточный результат без хранения в базе данных и отображения на форме. Что вполне достаточно для получения результата моей первоначальной задачи.
