Срочно-зависимые складки

Question

Позвольте мне объяснить, что я имею в виду с помощью чувствительной к стоимости складки с примером: вычисление pi с произвольной точностью. Мы можем использовать Leibniz formula (не очень эффективные, но хорошие и простые) и ленивые списки, как это:

pi = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i<-[0..]] 

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

pi' n = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i<-[0..n]] 

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

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

Редактировать: Было бы здорово иметь экономичные складки, которые могли бы также учитывать время вычисления/потребления энергии. Например, я хочу получить самое точное значение pi, учитывая, что у меня есть 1 час времени вычисления и 10kW-hrs, чтобы потратить. Но я понимаю, что это уже не будет строго функциональным.

Answer 1

Моя рекомендация - использовать сканирование вместо складки. Затем перейдите в результирующий список, пока не найдете нужную вам точность. Полезный частный случай левого сканирования (scanl) является iterate функцией:

piList :: [Double] 
piList = 
    map (4*) . 
    scanl (+) 0 . 
    map recip . 
    iterate (\x -> -(x + 2 * signum x)) $ 1 

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

findPrec :: (Num a, Ord a) => a -> [a] -> Maybe a 
findPrec p (x0:x1:xs) 
    | abs (x1 - x0) <= p = Just x0 
    | otherwise   = findPrec p (x1:xs) 
findPrec _ _ = Nothing 

Answer 2

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

import Data.List (findIndex) 
pis = scanl (+) 0 [4*(-1)**i/(2*i+1) | i <- [0..]] 
accuracies = zipWith (\x y -> abs (x-y)) pis (tail pis) 
piToWithin epsilon = case findIndex (<epsilon) accuracies of 
    Just n -> pis !! n 
    Nothing -> error "Wow, a non-terminating loop terminated!" 

Answer 3

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

Существует, однако, общее правило, что если числовой процесс имеет предел, то числовые сдвиги приближаются к нулю как грубая геометрическая прогрессия, поэтому, если два последующих сдвига равны 1,5 и 1,0, тогда следующий сдвиг будет где-то около 0,6 и т. д. (лучше накапливать такую ​​оценку по нескольким последним членам списка, а не только по 2 члена). Используя это правило и уравнение для суммы геометрической прогрессии, вы обычно можете найти разумную оценку для числовой точности. Примечание: это эмпирическое правило (у него есть имя, но я его забыл), а не строгая теорема.

Кроме того, представление IEEE Double/Float имеет ограниченную точность и в какой-то момент добавление небольших чисел из хвоста последовательности не изменит вычисленную частичную сумму. Вам рекомендуется прочитать о представлении с плавающей запятой в x86 для этого случая, вы можете найти свою складку.

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

Answer 4

Некоторые хорошие примеры того, что Daniel Wagner предполагает выше, можно найти в статье Why Functional Programming Matters

Конкретными примерами из статьи являются: итеративный поиск корней, числовое дифференцирование и числовая интеграция.