Каковы лучшие (портативные) кроссплатформенные математические библиотеки произвольной точности? [закрыто]

81

Я ищу хорошую математическую библиотеку произвольной точности на C или C ++. Не могли бы вы дать мне несколько советов или предложений?

Основные требования:

  1. Он должен обрабатывать сколь угодно большие целые числа - меня больше всего интересуют целые числа. В случае, если вы не знаете, что означает слово «произвольно большой», представьте себе что-то вроде 100000! (факториал 100000).

  2. Точность не требуется указывать во время инициализации библиотеки или создания объекта. Точность должна только быть ограничена имеющимися ресурсами системы.

  3. Он должен использовать всю мощь платформы и изначально обрабатывать «небольшие» числа. Это означает, что на 64-битной платформе при вычислении (2 ^ 33 + 2 ^ 32) должны использоваться доступные 64-битные инструкции ЦП. Библиотека не должна рассчитывать это так же, как с (2 ^ 66 + 2 ^ 65) на той же платформе.

  4. Он должен эффективно обрабатывать сложение ( +), вычитание ( -), умножение ( *), целочисленное деление ( /), остаток ( %), мощность ( **), приращение ( ++), декремент ( --), НОД, факториал и другие общие целочисленные арифметические вычисления. Возможность обрабатывать такие функции, как квадратный корень и логарифм, которые не дают целочисленных результатов, является плюсом. Способность обрабатывать символьные вычисления еще лучше.

Вот что я нашел на данный момент:

  1. Java «s BigInteger и BigDecimal класс: Я использую это до сих пор. Я прочитал исходный код, но не понимаю математики под ним. Возможно, это основано на теориях и алгоритмах, которым я никогда не учился.

  2. Встроенный целочисленный тип или основные библиотеки bc , Python , Ruby , Haskell , Lisp , Erlang , OCaml , PHP , некоторых других языков: я использовал некоторые из них, но не знаю, какую библиотеку они используют, или какую реализацию они используют.

Что я уже знал:

  1. Используется charдля десятичных цифр и char*для десятичных строк, а вычисления цифр forвыполняются с помощью -loop.

  2. Использование int(или long int, или long long) в качестве базовой «единицы» и массива этого типа в качестве произвольного длинного целого числа и выполнение вычислений с элементами с использованием for-loop.

  3. Использование целочисленного типа для хранения десятичной цифры (или нескольких цифр) как BCD (десятичное число с двоичным кодом) .

  4. Алгоритм умножения Бута .

Чего я не знаю:

  1. Печать упомянутого выше двоичного массива в десятичном виде без использования наивных методов. Пример наивного метода: (1) сложить биты от младшего к старшему: 1, 2, 4, 8, 16, 32,… (2) использовать char*-строку, упомянутую выше, для хранения промежуточных десятичных результатов).

Что я ценю:

  1. Хорошие сравнения GMP , MPFR , decNumber (или других, на ваш взгляд, хороших библиотек).

  2. Хорошие предложения по книгам и статьям, которые я должен прочитать. Например, иллюстрация с фигурами в то, как не-наивные преобразованиях алгоритма работа двоичных к-десятичном будет хорошо. Статья Дугласа У. Джонса « Преобразование двоичного числа в десятичное с ограниченной точностью » является примером хорошей статьи.

  3. Любая помощь в целом.

Пожалуйста , не отвечайте на этот вопрос, если считаете, что с помощью double(или long double, или long long double) можно легко решить эту проблему. Если вы так думаете, значит, вы не понимаете, о чем идет речь.

c++ c biginteger bigdecimal gmp Сиу Чинг Понг -Асука Кенджи-
источник
3
Насколько я понимаю, GMP кажется хорошей библиотекой. Что меня интересует, так это почему разработчикам Python / Haskell / Erlang / и т. Д. Необходимо заново изобретать колесо. Если GMP настолько хорош, почему бы не полагаться на него? Лицензия GPL / LGPL может быть одной из проблем, но, несмотря на это (а также на проблему с режимом округления), есть ли другие недостатки GMP? Является ли встроенное целое число в Python / Haskell / Erlang / любой криптографической библиотеке быстрее, чем GMP? Если да, я хотел бы извлечь и использовать его, если позволяет лицензия.
Сиу Чинг Понг - Асука Кенджи -
На cs.uiowa.edu/~jones/bcd/decimal.html я нашел хорошую статью Дугласа У. Джонса. В статье описывается метод преобразования 16-разрядного целого числа в десятичное представление с использованием только 8-разрядной целочисленной арифметики. Идея состоит в том, чтобы разбить 16-битное число на 4 полубайта, каждый из которых представляет «цифру» по основанию 16. Итак, цифра-0 (n0) представляет x1, n1 => x16, n2 => x256, n3 => x4096. Тогда очевидно, что цифра-0 десятичного числа (d0) является цифрой-0 результата n0 * 1 + n1 * 6 + n2 * 6 + n3 * 6. При правильной обработке переноса с d1 на d4 можно также быть вычисленным.
Сиу Чинг Понг - Асука Кенджи -
Однако, насколько я мог себе представить, идею Дугласа нельзя было расширить для обработки произвольно длинных двоичных целых чисел. Это потому, что числа 1 (16 ^ 0), 16 (16 ^ 1), 256 (16 ^ 2) и 4096 (16 ^ 3) предварительно вычислены. Тогда проблема заключается в том, как представить 16 ^ n в десятичном виде для сколь угодно большого n.
Сиу Чинг Понг - Асука Кенджи -

Ответы:

24

GMP - популярный выбор. В Squeak Smalltalk есть очень хорошая библиотека, но она написана на Smalltalk.

Вы просили соответствующие книги или статьи. Сложная часть bignum - деление в столбик. Я рекомендую статью Пера Бринча Хансена « Возвращение к разделу множественной длины: обзор минного поля» .

Норман Рэмси
источник
Спасибо за ссылку на статью! Да, я согласен, что разделение - самая сложная часть. Я знал, как делать деление вручную, используя "методы бумаги и карандаша" :-), и, таким образом, тот же метод можно применить к десятичной строке char *(каждая charпредставляет собой десятичную цифру) или к int *строке BCD ( каждая intпредставляет 4/8/16 цифр BCD). Однако мне интересно, имитируют ли библиотеки реального уровня производства "метод бумаги и карандаша", поскольку он слишком медленный.
Сиу Чинг Понг - Асука Кенджи -
Чтобы понять почему, давайте представим, как это работает 100,000,000,000,000,000 / 333,333,333,333: Первый шаг - сравнить 100,000,000,000с 333,333,333,333. Поскольку первое меньше второго, расчет просто переходит к следующей цифре. Второй шаг - найти частное от 1,000,000,000,000 / 333,333,333,333, это включает либо умножение 333,333,333,333 * 1(и * 2, * 3и * 4) методом проб и ошибок , либо последовательное вычитание в цикле. Вы видите, насколько он медленный? Я считаю, что существуют более эффективные алгоритмы.
Сиу Чинг Понг - Асука Кенджи -
3
@Sui: Бринч Хэнсон показывает, как можно сократить метод проб и ошибок максимум до двух испытаний. Это действительно очень впечатляет.
Норман Рэмси,
Хорошо, позвольте мне более подробно ознакомиться с бумагой. Спасибо!
Сиу Чинг Понг - Асука Кенджи -
1
Я не уверен, где вы нашли свое решение, и какой формат вы использовали для хранения цифр, но формат COBOL COMP-3 nybble намного приятнее, поскольку он более компактен, каждый 4 бита хранит 0-9 value, AND, вам не нужно вычитать шестнадцатеричное 30 из значения символа ASCII, чтобы получить полезную цифру.
13

В целом, GMP является самой быстрой универсальной библиотекой произвольной точности . Если вы хотите работать со значениями с плавающей запятой, посмотрите библиотеку MPFR . MPFR основан на GMP.

Что касается встроенной поддержки произвольной точности на других языках, Python использует свою собственную реализацию из-за лицензии, размера кода и переносимости кода. Модуль GMPY позволяет Python получить доступ к библиотеке GMP.

casevh
источник
Благодарю за ваш ответ! Вы упомянули «переносимость кода». Не могли бы вы объяснить, в чем проблема? Я думал, что GMP переносим и поддерживается на основных платформах ...
Сиу Чинг Понг - Асука Кенджи -
2
«переносимость кода» - это не то же самое, что «поддерживается на основных платформах». Python использует простую реализацию, которая делает очень мало предположений о поведении компилятора C, поэтому один и тот же код может компилироваться практически на любом компиляторе C. GMP использует больше кода (C и тщательно настроенная сборка), который делает GMP быстрее, но также делает больше предположений о поведении компилятора C и ассемблера. Например, GMP плохо поддерживается компиляторами Microsoft Visual Studio. Существует ветвь GMP под названием MPIR (www.mpir.org), которая поддерживает компиляторы Microsoft.
casevh
Понимаю. Это означает, что реализация Python больше похожа на ANSI C, в то время как реализация GMP использует трюки __asm ​​... Спасибо за ваши объяснения.
Сиу Чинг Понг - Асука Кенджи -
8

См. TTMath , небольшую шаблонную библиотеку только для заголовков, бесплатную для личного и коммерческого использования.

Андрей Сырокомский
источник
Привет! Это простая в использовании библиотека, и кажется, что она использует мощность процессора и использует некоторую магию шаблонов C ++ для завершения работы. Отличная библиотека! +1 для вас!
Сиу Чинг Понг - Асука Кенджи -
Да, и у него есть разрешающая лицензия BSD без авторского лева.
Plasmacel 02
Со страницы выше: «Насколько большими могут быть значения, устанавливается во время компиляции». - значит, это не соответствует требованиям.
osxdirk
7

Я сам не сравнивал между собой арифметические библиотеки произвольной точности, но люди, которые, похоже, более или менее единообразно придерживаются GMP. Как бы то ни было, целые числа произвольной точности в GHC Haskell и GNU Guile Scheme реализованы с использованием GMP, а самая быстрая реализация теста pidigits для языковой выборки основана на GMP.

Ричард Баррелл
источник
Благодаря! ^ ___ ^ Хорошая информация!
Сиу Чинг Понг - Асука Кенджи -
4

А что насчет Пари ? Он построен на основе GMP и предоставляет все другие полезные свойства операций с теорией чисел, которые вам когда-либо понадобятся (и многие вещи для символических вычислений).

Фортран
источник
Привет, фортран (!), Выглядит неплохо! Спасибо за информацию!
Сиу Чинг Понг - Асука Кенджи -
Добро пожаловать :-) Также с Pari вы можете создавать быстрые прототипы с помощью GP, и когда вы будете довольны, напишите оптимизированную версию C (и я думаю, что она поставляется с компилятором GP-> C, чтобы помочь с этим)
fortran,