SNAPKITTYWEST's picture
montrepol: exact mathematics in Haskell, with proofs and a certifying solver
5316c4e verified
Raw History Blame Contribute Delete
2.73 kB
-- SPDX-License-Identifier: AGPL-3.0-or-later
module Main (main) where
import MP.Algebra
import MP.Check
import MP.Recurrence
main :: IO ()
main =
runSuite
"mp-seq"
[ prop "SQ-01" "BM's polynomial regenerates the sequence over GF(2)" (listUpTo 40 gf2) regenerates
, prop "SQ-01" "BM's polynomial regenerates the sequence over Q" (listUpTo 14 (rationalIn (-5) 5 3)) regenerates
, propN "SQ-02" "BM is minimal: no shorter LFSR generates the sequence (GF(2), brute force)" 300 (listUpTo 11 gf2) minimal
, propN "SQ-03" "a length-l LFSR is recovered from 2l terms and predicts the rest (Massey)" 300 genLFSR recovered
, unit "SQ-04" "x^5 + x^2 + 1 is primitive: period 31, linear complexity 5" $
let c = map GF2 [True, False, True, False, False, True] -- 1 + x^2 + x^5
s = runLFSR c (map GF2 [True, False, False, False, False]) 62
in period c (take 5 s) 100 === Just 31 .&&. fst (berlekampMassey s) === 5
, unit "SQ-04" "x^4 + x^2 + 1 = (x^2 + x + 1)^2 is not primitive: period 6, not 15" $
let c = map GF2 [True, False, True, False, True]
in period c (map GF2 [True, False, False, False]) 100 === Just 6
, unit "SQ-05" "Fibonacci over Q has connection polynomial 1 - x - x^2" $
berlekampMassey (take 20 fibs) === (2, [1, -1, -1])
, unit "SQ-05" "the zero sequence has linear complexity 0" $
berlekampMassey (replicate 10 (0 :: Rational)) === (0, [1])
]
where
fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs) :: [Rational]
gf2 :: Gen GF2
gf2 = GF2 <$> boolG
regenerates :: (Field a, Show a) => [a] -> Result
regenerates s =
let (l, c) = berlekampMassey s
in assert ("C = " <> show c <> " does not generate it") (generates c s)
.&&. length c === l + 1
.&&. assert "L > length" (l <= length s)
-- Every connection polynomial over GF(2) of degree at most l.
allPolys :: Int -> [Poly GF2]
allPolys l = map (one :) (mapM (const [GF2 False, GF2 True]) [1 .. l])
minimal :: [GF2] -> Result
minimal s =
let (l, _) = berlekampMassey s
shorter = [c | k <- [0 .. l - 1], c <- allPolys k, generates c s]
in assert ("a length " <> show (map (subtract 1 . length) shorter) <> " LFSR exists") (null shorter)
genLFSR :: Gen ([GF2], [GF2])
genLFSR = do
l <- intIn 1 8
taps <- listOfLength l gf2
initial <- listOfLength l gf2
pure (one : taps, initial)
recovered :: ([GF2], [GF2]) -> Result
recovered (c, initial) =
let l = length initial
long = runLFSR c initial (6 * l)
(l', c') = berlekampMassey (take (2 * l) long)
in assert ("complexity " <> show l' <> " exceeds " <> show l) (l' <= l)
.&&. assert ("recovered " <> show c' <> " fails beyond 2l") (generates c' long)