Точная реальная арифметическая и ленивая производительность списков в C ++ / Haskell - PullRequest
Новая
       33

Точная реальная арифметическая и ленивая производительность списков в C ++ / Haskell

13 голосов
/ 04 июня 2011

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

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

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

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

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

Любой вклад приветствуется!

Ответы [ 2 ]

8 голосов
/ 04 июня 2011

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

Ленивые потоки наиболее эффективно представлены в виде данных с компонентами отложенной функции. Это представление, которое использует довольно эффективная реализация на Haskell в GHC, и в любом случае вам придется использовать ее в C ++. Нет специальной «быстрой» версии лени, которую вы могли бы написать на C ++, которая не была бы опробована в течение 20 лет исследований компилятора на Haskell, и более того, возвращаясь к Algol.

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

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

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

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

5 голосов
/ 04 июня 2011

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

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

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

  • , что не означает, что алгоритмы будут простыми.Подумайте, как обработать текущий результат 99999 в дополнение.Вы должны быть готовы к тому, что все 9 будут волноваться за перенос. Теперь попробуйте подумать о том, как сделать умножение.Язык с ленивым выражением может помочь выразить его, но тогда вы столкнетесь с проблемой первой проблемы;Я был бы счастлив узнать, что компиляторы могут оптимизировать его, но я боюсь, что это не так.

...