«Бесконечная» точность, взаимная в Хаскеле - PullRequest
Новая
       89

«Бесконечная» точность, взаимная в Хаскеле

0 голосов
/ 18 февраля 2019

Мне нужно сгенерировать бесконечный список Haskell, содержащий все биты (или слова) из дробной части обратной части целого числа, в MSB-первом порядке.Есть ли простой способ сделать это из стандартных библиотек, или мне нужно реализовать итерационную функцию Ньютона или подобное?

Я рассмотрел использование CReal, но не могу найти способ извлечения битов / слов.

Ответы [ 3 ]

0 голосов
/ 18 февраля 2019

В моем другом ответе я покажу, как это сделать с 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
0 голосов
/ 19 февраля 2019

После небольшого количества попыток мне удалось сделать это, не прибегая к 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'

Использование явной рекурсии дает умеренное ускорение по сравнению с использованием итерации.Я не слишком беспокоюсь о том, где он входит в цикл, поскольку я использую его с такими большими числами, что я никогда не достигну цикла.Еще раз спасибо за помощь!

0 голосов
/ 18 февраля 2019

Есть более принципиальные способы, но 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 на любую базу, какую пожелаете.

...