4

コストに敏感なフォールドの意味を例を挙げて説明しましょう。任意精度で円周率を計算します。ライプニッツの公式（あまり効率的ではありませんが、素晴らしくシンプルです）と次のような怠惰なリストを使用できます。

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

さて、無限リスト内のすべての値を計算する必要があるため、明らかにこの計算は完了しません。しかし実際には、円周率の正確な値は必要ありません。指定された小数点以下の桁数だけが必要です。私はこのように円周率を定義することができます：

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

しかし、必要な精度を得るために渡す必要があるnの値はまったくわかりません。私が必要としているのは、必要な精度を達成するたびに折り畳みを停止する、ある種のコストに敏感な折り畳みです。そのような折り目は存在しますか？

（この場合、必要な精度が達成されたかどうかを簡単に確認できます。ライプニッツの式では、各項の符号が交互になるシーケンスが使用されるため、誤差は常に次の項の絶対値よりも小さくなります。順序。）

編集：計算時間/消費電力も考慮することができるコストに敏感なフォールドがあるのは本当にクールでしょう。たとえば、1時間の計算時間と10kW-hrsを費やすとすると、piの最も正確な値が必要です。しかし、これはもはや厳密には機能しないことを私は理解しています。

4

4 に答える 4

10

フォールドの代わりにスキャンを使用することをお勧めします。次に、必要な精度が見つかるまで、結果のリストをトラバースします。左スキャン（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
于 2012-08-01T20:26:27.260 に答える
4

これを行う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!"
于 2012-08-01T20:21:42.723 に答える
2

一般的に、あなたが求める折り目は存在しません。精度の見積もりを自分で提供する必要があります。これは一般的に問題になる可能性がありますが、実際に役立つすべてのシーケンスには、通常は他の誰かが取得する部分和の数値精度の妥当な上限推定値があります。ただし、数値解析の教科書など、通常は無限の数列の合計を推定し、それに上限を与えることについての部分がある関連する教科書を読むことをお勧めします。

ただし、一般的な規則として、数値プロセスに制限がある場合、数値シフトは大まかな等比数列としてゼロに近づくため、後続の2つのシフトが1.5と1.0の場合、次のシフトは約0.6などになります（ 2人のメンバーだけでなく、いくつかの最後のメンバーリストにそのような見積もりを蓄積することをお勧めします）。等比数列の合計にこの規則と方程式を使用すると、通常、数値精度の妥当な見積もりを見つけることができます。注：これは経験則であり（名前はありますが、忘れてしまいました）、厳密な定理ではありません。

さらに、IEEE Double / Floatの表現は精度が制限されており、ある時点でシーケンスの末尾から小さな数値を追加しても、計算された部分和は変更されません。この場合、x86での浮動小数点表現について読むことをお勧めします。折り目が見つかる場合があります。

要約：一般的な解決策はありませんが、通常、最も有用なシーケンスについては実際には合理的な見積もりがあり、通常、各シーケンスタイプの文献またはハードウェアの数値制限から取得されます。

于 2012-08-01T20:32:36.473 に答える
1

Daniel Wagnerが上記で示唆していることのいくつかの良い例は、関数型プログラミングが重要である理由の論文にあります。

この論文の具体例は、反復求根アルゴリズム、数値微分、数値積分です。

于 2012-08-02T17:37:27.757 に答える