Поплавки против рациональных чисел в произвольной точности дробной арифметики (C/С++)

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

Я знаю существующие библиотеки C/С++, некоторые из которых предлагают дробный APA с "float" и другие с рациональными (ни один из них не имеет APA с фиксированной точкой), и, конечно, я мог бы тестировать библиотеку, которая полагается на реализацию "float" против той, которая использует рациональную реализацию, но результаты во многом будут зависеть от деталей реализации этих конкретных библиотек, которые я должен был бы выбрать случайным образом из почти десяти доступных. Так что это более теоретические плюсы и минусы двух подходов, которые меня интересуют (или три, если принять во внимание APA с фиксированной точкой).

Ответ 1

Вопрос в том, что вы подразумеваете под произвольной точностью, которую вы упоминаете в названии. Означает ли это "произвольный, но заранее определенный во время компиляции и фиксированный во время выполнения"? Или это означает "бесконечный, то есть расширяемый во время выполнения для представления любого рационального числа"?

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

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

Заметим также, что во многих практических приложениях операции умножения часто сопровождаются операциями деления (как в x = y * a / b), которые "компенсируют" друг для друга, что означает, что часто нет необходимости выполнять какие-либо корректировки для таких умножений и делений. Это также способствует эффективности арифметики с фиксированной точкой.

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

Итак, опять же, почему вы рассматриваете только плавающие и рациональные представления. Есть ли что-то, что мешает вам рассматривать представление с фиксированной точкой?

Ответ 2

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

Для простого сложения и вычитания вам не нужны умножения для float ^* и 3 умножения на рациональные. Поплавки опускают руки вниз.

Для умножения вам нужно одно умножение для float и 2 умножения для рациональных чисел. Поплавки имеют край.

Дивизия немного сложнее, и здесь можно выиграть рациональность, но это отнюдь не является несомненным. Я бы сказал, что это ничья.

Таким образом, IMHO, тот факт, что добавление не менее O(n*log(n)) для рациональных и O(n) для float явно дает выигрыш для представления с плавающей запятой.

^* Возможно, вам понадобится одно умножение для выполнения сложения, если ваша база экспонентов и ваша база цифр различны. В противном случае, если вы используете мощность 2 в качестве базы, то выравнивание операндов немного сдвигается. Если вы не используете силу из двух, вам также может потребоваться умножение на одну цифру, что также является операцией O(n).

Ответ 3

Поскольку никто другой, казалось, не упоминал об этом, рациональные и поплавки представляют разные наборы чисел. Значение 1/3 может быть представлено точно с помощью рационального, но не плавающего. Даже произвольный прецизионный поплавок принимает бесконечно много бит мантиссы, чтобы представить повторяющееся десятичное число, подобное 1/3. Это связано с тем, что поплавок эффективно, как рациональный, но где знаменатель ограничен степенью 2. Произвольная рациональность по точности может представлять все, что может иметь произвольный прецизионный float, и многое другое, поскольку знаменатель может быть любым целым числом, а не просто степенью of 2. (То есть, если я не ошибочно не понял, как реализованы произвольные прецизионные поплавки.)

Это ответ на ваше предложение о теоретических плюсах и минусах.

Я знаю, что вы не спрашивали об использовании памяти, но здесь теоретическое сравнение в случае, если кто-то еще заинтересован. Рационалы, как упоминалось выше, специализируются на числах, которые могут быть представлены просто в дробных обозначениях, таких как 1/3 или 492113/203233, а floats специализируются на числах, которые просто представляют в научной нотации с полномочиями 2, например 5*2^45 или 91537*2^203233. Количество символов ascii, необходимых для представления чисел в их соответствующей для человека форме, пропорционально их использованию в памяти.

Пожалуйста, исправьте меня в комментариях, если я ошибаюсь.

Ответ 4

Вы действительно задаете вопрос: "Мне нужно участвовать в гонке с моим избранным животным. Должен ли я выбирать черепаху или улитку?".

Первое предложение "emulating double" звучит как ступенчатая точность: использование массива удвоений, сумма которого является определенным числом. Существует статья Дугласа М. Приста "Алгоритмы произвольной точной арифметики с плавающей точкой", которая описывает, как реализовать эту арифметику. Я реализовал это, и мой опыт очень плохой: необходимые накладные расходы, чтобы этот прогон снизился до 100-1000 раз! Другой метод использования дробных чисел также имеет серьезные недостатки: вам нужно реализовать gcd и kgv, и, к сожалению, каждый штрих в вашем числителе или знаменателе имеет хорошую возможность взорвать ваши цифры и убить вашу производительность.

Таким образом, по моему опыту, это худший выбор, который можно сделать для производительности.

Я рекомендую использовать библиотеку MPFR, которая является одним из самых быстрых пакетов AP в C и С++.

Ответ 5

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

Лично я думаю, что в вашем случае AP floats будет более подходящим.