Haskell中的“无限”精度倒数

问题描述 投票:2回答:3

我需要生成一个无限的Haskell列表,其中包含来自Integer倒数的小数部分的所有位(或字),以MSB优先顺序排列。是否有一种直接的方法从标准库中执行此操作,还是需要实现牛顿迭代函数或类似函数?

我考虑过使用CReal,但找不到提取位/字的方法。

haskell arbitrary-precision
3个回答
2
投票

有更多原则性的方法,但CReal当然可以做到。

> bit n = (`mod` 2) . floor . (*2**n)
> [bit i (pi :: CReal) | i <- [-1..10]]
[1,1,0,0,1,0,0,1,0,0,0,0]
> [bit i (5/8 :: CReal) | i <- [1..10]]
[0,1,0,1,0,0,0,0,0,0,0]

无论你喜欢什么基地,都可以在任何地方换掉2。对于无限列表,迭代乘法可能更便宜,因此:

> bits = map ((`mod` 2) . floor) . iterate (2*)
> take 10 (bits (5/8 :: CReal))
[0,1,0,1,0,0,0,0,0,0]

再次,你可以换掉2任何你喜欢的基地。


2
投票

在我的另一个答案中,我展示了如何使用CReal来回答你是否可以做到的问题。但我实际上并不认为这是一个好主意,因为它比所需要的更多。只是为了说明我对“更有原则”的方法的想法,这就是我在想的:

bits :: Rational -> [Int]
bits n = whole : bits (2*frac) where
    (whole, frac) = properFraction n

在行动:

> take 65 . bits $ 1/3
[0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]

您会注意到,这在另一个答案中明显快于CReal方法。即使你将另一个答案从CReal切换到Rational,它也应该具有更好的内存性能,因为它将分数上限保持为1(而另一个解决方案每次迭代增加~1位)。通过注意它何时开始循环,它可以更快地制作。这是一个以易于观察的方式返回循环的函数:

import Data.Set (Set)
import qualified Data.Set as S

data BitsRep
    = Loop Rational [Int]
    | Lollipop [Int] [Int]
    deriving (Eq, Ord, Read, Show)

-- always returns a Lollipop when given an empty set
bitsRaw :: Set Rational -> Rational -> BitsRep
bitsRaw s n = case S.member n s of
    True -> Loop n []
    False -> case bitsRaw (S.insert n s) (2*frac) of
        Lollipop prefix loop -> Lollipop (whole:prefix) loop
        Loop n' loop -> (if n == n' then Lollipop [] else Loop n') (whole:loop)
        where
        (whole, frac) = properFraction n

如果你真的希望它作为一个无限列表,那么一个短包装器就可以了,并且一旦达到循环点就显着减少了所需的计算:

bits :: Rational -> [Int]
bits n = prefix ++ cycle loop where
    Lollipop prefix loop = bitsRaw S.empty n

2
投票

经过一些修补,我设法做到了这一点,而没有诉诸Rational / CReal:

recipBits :: Integer -> [Bool]
recipBits n = dblAndMod2 2
    where dblAndMod2 :: Integer -> [Bool]
          dblAndMod2 !r = let bit = r >= n
                              r'  = 2 * (if bit then r - n else r)
                          in  bit : dblAndMod2 r'

使用显式递归比使用迭代获得适度的加速。我并不太担心它进入循环的位置,因为我使用它的数量如此之多,以至于我永远无法进入循环。再次感谢您的帮助!

© www.soinside.com 2019 - 2024. All rights reserved.