ОБЗОР СУЩЕСТУЮЩИХ БИБЛИОТЕК ДЛИННОЙ АРИФМЕТИКИ

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

разных языках программирования для выполнения таких расчетов. При этом возникает проблема выбора инструментария, наиболее подходящего для решения конкретных прикладных задач в каждом случае.

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

Все множество предлагаемых библиотек можно классифицировать по нескольким параметрам. Первый - лицензия, под которой распространяется программный продукт. Ее необходимо учитывать при публикации своих исследований, проведенных с использованием той или иной библиотеки. Различают коммерческие (IMSL), бесплатные для некоммерческого использования (LiDIA, MIRACL) и бесплатные (GMP, NTL, CLN, MPI, Imath) программные продукты. Следует отметить, что распространяемых под различными разновидностями свободных лицензий программных продуктов сейчас значительно больше, нежели коммерческих. Причиной тому является то, что большая часть таких библиотек создавалась в стенах университетов в приложении к различным научным проектам. Впоследствии

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

– целые числа произвольной длины (знаковые и беззнаковые);

– рациональные дроби;

– числа с плавающей точкой произвольной точности;

– комплексные числа;

– векторы;

– матрицы;

– полиномы.

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

GMP - это свободная библиотека длинной арифметики, поддерживающая работу со знаковыми целыми, рациональными числами и числами с плавающей запятой. Преимущества GMP:

– практически не имеет ограничений точности вычислений, кроме ограниченного объема доступной памяти;

– имеет богатый набор функций и удобный интерфейс;

– поддерживает большинство современных платформ: Unix-подобные операционные системы, такие как GNU/Linux, Solaris, HP-UX, Mac OS X/Darwin, BSD, AIX; Windows. Существуют 32-разрядная и 64-разрядная версии GMP;

– допускает использование наиболее эффективных алгоритмов и оптимизированного под различные современные процессорные системы ассемблерного кода во всех внутренних циклах.

GMP является одной из самых быстрых на сегодняшний день библиотек длинной арифметики. Основные области применения библиотеки – это криптографические системы и исследования, обеспечение безопасности межсетевых взаимодействий, алгебраические пакеты. Библиотека GMP является частью проекта GNU.

CLN – это библиотека для расчетов с использованием всех существующих числовых типов. В этой библиотеке реализованы классы для таких типов данных, как: целые числа, рациональные дроби, числа с плавающей точкой, комплексные числа, унивариантные полиномы, вычисления по модулю. CLN использует GMP в качестве вычислительного ядра и незначительно уступает ей в скорости расчетов. Богатый набор поддерживаемых типов, удобный программный интерфейс, прозрачные механизмы взаимодействия и преобразования друг в друга различных

структур данных вместе с достаточно высокой скоростью вычислений обеспечивают широкую распространенность данной библиотеки. CLN лежит в основе многих программных продуктов, связанных с научными исследованиями и математическими расчетами: Scilab, Octave (свободные аналоги MatLAB), maxima (пакет для алгебраических вычислений, сво-

бодный аналог MAPLE) и др.

NTL – это высокопроизводительная библиотека C++, предоставляющая структуры данных и алгоритмы для работы с целыми произвольной длины, векторами, матрицами, полиномами, числами с плавающей точкой произвольной точности. Полиномиальная арифметика в NTL – одна из самых быстрых на сегодняшний день. Она не раз использовалась при становлении «мировых рекордов» в скорости алгоритмов факторизации и определении порядка эллиптических кривых. Все алгоритмы NTL реализованы на C++, что обеспечивает высокую мобильность данной библиотеки. Несмотря на наличие собственного вычислительного ядра, NTL позволяет использовать вместо него библиотеку GMP.

MIRACL - единственная из перечисленных библиотек, распространяемая под коммерческой лицензией. Однако авторами разрешается использование MIRACL для некоммерческих нужд. Основные

преимущества данной библиотеки:

– наличие реализованных C/C++ интерфейсов «из коробки»;

– богатая библиотека специализированных функций для вычислений в области эллиптической криптографии;

– наличие различных алгоритмов решения одних и тех же задач с возможностью выбора оптимального варианта для текущих нужд. [1]