В чем разница между реализациями «Rational» и «BigNum»

Таких типов очень много для многих языков. Насколько я знаю, вот как это работает.

Rational просто хранит две отдельные цифры для числителя и знаменателя (например, 3 и 10 для 0,3).

BigNum хранит каждую цифру числа в каком-то «массиве» и выполняет арифметику столбцов, как это обычно делают люди. Например, 0,1 сохраняет как [0, '.', 1]. Если мы захотим добавить к нему 0,2, получится что-то вроде этого:

  [0, '.', 1]
+ [0, '.', 2]
= [0, '.', 3]

Я прав? Есть ли другая популярная арифметика произвольной точности? Если да, то как он называется?

Я не говорю о какой-то конкретной реализации, а скорее об общей идее того, что она обычно делает.


precision floating-point bignum arbitrary-precision rational-number
person FrozenHeart    schedule 12.08.2016    source источник
comment
Я не знаю внутренностей BigNum, но сомневаюсь, что десятичные дроби хранятся в виде текста. Дело в том, что BigNum используется для десятичных значений, а Rational — для дробей (рациональных чисел). Rational подходит для таких значений, как 1/3, потому что для рациональных чисел 1/3 * 6 действительно возвращает 2.   -  person Rudy Velthuis    schedule 13.08.2016
comment
@Rudy Velthuis И когда тогда я должен предпочесть BigNum вместо Rational?   -  person FrozenHeart    schedule 13.08.2016
comment
Для значений, которые вы получаете в виде десятичной строки или целого числа и т. д., BigNum, скорее всего, более эффективен.   -  person Rudy Velthuis    schedule 13.08.2016
comment
@Rudy Velthuis Для значений, которые вы получаете в виде десятичной строки, некоторые реализации Rational также принимают десятичные строки   -  person FrozenHeart    schedule 13.08.2016
comment
конечно, но, как я уже сказал, BigNum, вероятно, более эффективен.   -  person Rudy Velthuis    schedule 13.08.2016
comment
@Rudy Velthuis Почему ты так думаешь?   -  person FrozenHeart    schedule 13.08.2016
comment
Я реализовал оба на другом языке. Я предполагаю, что они работают аналогично. В частности, для десятичных и целых чисел BigNum не нужно делать много работы, которую должен делать Rational. В большинстве реализаций Rational с множественной точностью для внутреннего использования используются BigInteger, BigDecimal или BigNum.   -  person Rudy Velthuis    schedule 13.08.2016
comment
FWIW, BigNum (или BigDecimal) обычно хранит 0,3 как целое число (или BigInteger) 3, масштабированное по показателю степени -1, то есть как 3 * 10 ^ -1. 17,345 хранится как 17345 * 10^-3 (целое число 17345, показатель степени -3). Показатель степени также может быть отрицательным или называться шкалой.   -  person Rudy Velthuis    schedule 13.08.2016

Ответы (1)


arrow_upward
1
arrow_downward

Широко используются несколько различных подходов:

  • Целые числа произвольной точности обычно хранятся в виде массива целых чисел. Примеры: длинные целые числа в Python, BigInteger в Java или mpz в библиотеке GMP (и таких языках, как Julia и Mathematica, которые используют GMP).

  • Поплавки произвольной точности хранятся как целое число произвольной точности и показатель степени. Это доступно как:

    • base-2 (e.g. mpf in GMP, MPFR and languages which uses these libraries): tend to be favoured in technical and numerical areas as they act exactly like normal floating point numbers but with extra precision (so can be used to verify methods or calculations).
    • base-10 (например, BigDecimal в Java, decimal в Python.) Как правило, предпочтение отдается финансовым приложениям (поскольку их меньше беспокоится об округлении для валют), и люди, которые не могут понять тот факт, что 0.1 + 0.2 != 0.3 (исходя из частоты, с которой они излишне пропагандируются в StackOverflow).

  • Rationals (например, mpq в GMP, fractions в Python) хранит число как отношение (обычно) целых чисел произвольной точности. Это хорошо, поскольку результаты элементарных арифметических операций (+, -, *, /) всегда точны, даже для таких вещей, как x/3. Недостатком является то, что они не работают для нерациональных функций (таких как sqrt или sin) и могут быстро взорваться, если не используются осторожно (например, если используются в итеративном алгоритме, таком как метод Ньютона).

  • двойная двойная арифметика сохраняет число как пару с плавающей запятой номера (обычно C doubles, отсюда и название). Идея состоит в том, что второй элемент пары меньше, чем единица на последнем месте первого , так что вы эффективно удвоили доступную точность. Эти идеи восходят к статье Dekker (1971). и может быть расширен до трипл-дабл и квад-дабл. Преимущество заключается в том, что они могут использовать существующее аппаратное обеспечение с плавающей запятой, поэтому могут быть намного быстрее, чем произвольные числа с плавающей запятой, однако недостатком является то, что диапазон экспоненты остается таким же, как и в базовом формате с плавающей запятой (и точность по-прежнему фиксирована, поэтому действительно «произвольно»). Я не уверен, какие библиотеки широко используются, но у David Bailey есть хорошее резюме его программного обеспечения.

person Simon Byrne    schedule 15.08.2016