Точная реальная арифметика и ленивый список в С++/Haskell

Недавно я натолкнулся на предмет точной реальной арифметики после прочтения этой статьи и этот документ.

Я нашел ряд работ, в которых обсуждаются реализации точной арифметики с использованием сигнальных потоков. Использование бесконечных потоков для произвольной точности приводит к хорошим практическим реализациям на функциональных языках, таких как Haskell, с использованием ленивых списков. Тем не менее, документы, в которых обсуждаются такие реализации на функциональных языках, похоже, пришли к выводу, что производительность очень плохая.

Теперь я понимаю, что точные, не-аппаратные реализации, как правило, имеют относительно низкую производительность по сравнению со стандартным представлением с плавающей запятой, но я заинтересован в обеспечении более эффективной реализации на императивном языке (в частности, на С++) и сбор операций/функций (арифметические операции, тригонометрические функции, exp, log и т.д.).

Мой вопрос (ы): есть ли что-то по своей сути медленное в представлении с подписанным знаком/ленивым потоком, которое вызывает плохую производительность, или это Haskell? Что это мешает? Можно ли реализовать представление знакового символа с использованием ленивых потоков на С++, который обеспечивает (значительно) лучшую производительность, чем его коллега Haskell, или это упражнение бесполезно? Возможно, реконструировать как итерации?

Я знаю, существует две библиотеки С++, RealLib и iRRAM, которые обеспечивают эффективное вычисление реальных чисел. Однако они, похоже, используют интервальную арифметику, представляющую действительные числа как сокращающиеся вложенные интервалы, которые не кажутся "чистыми" подходами как бесконечные потоки (пожалуйста, исправьте меня, если вы не согласны!). Но, возможно, это единственные подходы, которые достигают хорошей эффективности?

Любой ввод оценивается!

Ответ 1

есть ли что-то по своей сути медленное представление о значении с символом/ленивым потоком, которое вызывает плохую производительность, или это Haskell? Что это мешает? Можно ли реализовать представление знакового символа с использованием ленивых потоков на С++, который обеспечивает (значительно) лучшую производительность, чем его коллега Haskell, или это упражнение бесполезно? Возможно, реконструировать как итерации?

Ленивые потоки представлены наиболее эффективно как данные с компонентами с задержкой. То, что представление представляет собой довольно эффективную реализацию Haskell в GHC, и тот, который вам нужно будет использовать на С++ в любом случае. Там нет специальной "быстрой" версии лени, которую вы могли бы написать на С++, которая еще не была опробована за 20 лет исследований компилятора Haskell и больше вернулась в Algol.

Подробнее о том, как наиболее эффективно реализовать ленивые структуры данных, см. Хороший вводный текст о реализации GHC?

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

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

Мое предположение - последние два момента. Версия лень для С++ будет только тяжелой работой, чтобы добраться до той же точки, на которой находится GHC, поэтому почему бы не поиграть с кодом из этой статьи и посмотреть, сможете ли вы сделать это быстрее.

Ответ 2

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

ленивая оценка означает, что в конечном итоге то, что вы думаете о числе, на самом деле представляет собой DAG, представляющую собой вычисление, ведущее к этому. Если запросить еще одну цифру, можно запрограммировать вычисления в каждом node этой DAG. В конце дня вы проводите гораздо больше времени в доме, чем в расчете.
вы, вероятно, не сможете использовать более сложные алгоритмы для базовых вычислений. Например, подход БПФ к умножению, очевидно, не может быть и речи.
что не означает, что алгоритмы будут простыми. Подумайте о том, как обрабатывать текущий результат 99999 в дополнение. Вам нужно быть готовым рябить перенос для всех этих 9. Теперь попробуйте подумать о том, как сделать умножение. Язык с ленивым выражением может помочь выразить это, но тогда вы столкнетесь с более сложной первой проблемой; Я был бы рад узнать, что компиляторы могут оптимизировать для него, но я боюсь, что это не так.