3

素数のリストと比較するためにフィボナッチ数のリストを生成しようとしています（例）。両方のリストは、最初の既知のfibo / prime番号で始まり、10000番目で終わります。問題は次のとおりです。グラフィカルな比較（グラフ）は、「logBase 2」などの関数がフィボナッチ数に適用されている場合にのみ可能ですが、「logBase」は「浮動」数でのみ機能します（？）。残念ながら、フィボナッチ数は膨大になるので、フィボナッチ数は「整数」（無制限）である必要があると思います。

これは変換の問題につながります。

例（Double対Integer対Rational）：

Prelude> (fromInteger 99^155 :: Double) 
Infinity

Prelude> 99^155
2105984461967288122980631709715261275645844225982779394351624787177327329412781425212770617487844004735075332631944629831514476725173837569097618069672639524362255333585985536520710945968603104880488606713054412670128838036813075895861981025491395960367363513228812061706617371582639821584522415306665565665499

Prelude> logBase 2 $ fromRational (fromInteger 99^155 :: Rational) 
Infinity

したがって、質問：「logBase」のような数学関数を使用して無制限の整数を処理するにはどうすればよいですか？いくつかのヒント？

4

1 に答える 1

2

log の数学的特性を使用するのはどうですか - のようなもの

{-# LANGUAGE ScopedTypeVariables #-}

logBaseRational :: forall a . (RealFloat a, Floating a) => Rational -> Rational -> a
logBaseRational k n | isInfinite (fromRational n :: a) = logBaseRational k (n/k) + 1
logBaseRational k n | isDenormalized (fromRational n :: a) = logBaseRational k (n*k) - 1
logBaseRational k n = logBase (fromRational k) (fromRational n)

非常に大きな数を処理する必要がある場合は、より効率的な方法を実行できますが、これは、関心のある範囲に対して行う必要があります。

の使用は、 andのテストが正しいタイプで実行さScopedTypeVariablesれるようにするためだけです。isInfiniteisDenormalized

また、isDenormalized範囲の下限の完全なテストではありません-必要なのは、(精度の問題が失われるため)両方をチェックすることと、変換され0ていない値がそうでないときに変換された値がそうであるかどうかを確認することです-しかし、これは質問は大きな数に関するものですが、それは重要ではありません。答えをより一般的にするために投げ込んだだけです。

于 2011-06-30T06:49:45.823 に答える