Haskell：我如何使用类似于“logBase”这样的数学函数来处理无界整数？

Question

Haskell：我如何使用类似于“logBase”这样的数学函数来处理无界整数？

4

我正在尝试生成一个斐波那契数列列表，以与质数列表进行比较（例如）。两个列表都从已知的第一个fibo / prime数字开始，并在第10000个数字结束。问题是：只有当应用了像“logBase 2”这样的函数时，才能进行图形比较（图表）斐波那契数，但是“logBase”仅适用于“浮点数”。不幸的是，斐波那契数变得非常巨大，因此我认为斐波那契数应该是“整数”（无界）。这导致了转换问题。例如（Double versus Integer versus Rational）：

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

Prelude> 99^155
2105984461967288122980631709715261275645844225982779394351624787177327329412781425212770617487844004735075332631944629831514476725173837569097618069672639524362255333585985536520710945968603104880488606713054412670128838036813075895861981025491395960367363513228812061706617371582639821584522415306665565665499

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

因此，问题是：如何使用像"logBase"这样的数学函数来处理无界整数？有什么提示吗？

- user445107

1

http://www.haskell.org/pipermail/haskell-cafe/2008-February/039493.html - Dan D.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- GS - Apologise to Monica · Accepted Answer

如何利用对数的数学属性？可以尝试以下方法：

{-# 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)

如果你需要处理非常大的数字，可以做一些更有效率的事情，但是这应该适用于你感兴趣的范围。

使用ScopedTypeVariables仅是为了确保在正确的类型上进行isInfinite和isDenormalized测试。

此外，isDenormalized并不是范围底部的完整测试 - 你想要检查的是，由于精度问题，转换后的值是否为0，而未转换的值不是 - 但由于这个问题只涉及大数值，所以这不重要，我只是为了让我的答案更加通用。