Download packages/mp-seq/test/Main.hs from SNAPKITTYWEST/montrepol: direct link, hf CLI and curl.
- Browser
- Download file 2.73 kB
-
https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/packages/mp-seq/test/Main.hs
- Command line
-
hf download hf://SNAPKITTYWEST/montrepol/packages/mp-seq/test/Main.hs
-
curl -L -o Main.hs https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/packages/mp-seq/test/Main.hs
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) | |