maximal length sequence
M系列に関する学習メモ*1。
import Test.HUnit import System.IO mulcon :: Int -> Int mulcon 0 = 1 mulcon n = (a * mulcon(n - 1) + b) `mod` m where a = 3 b = 0 m = 7 mc :: [Int] -> [Int] mc = map mulcon main :: IO (Counts, Int) main = runTestText (putTextToHandle stderr False) tests where x = mc [0 .. 11] tests = TestList [ "mc test" ~: x ~?= [1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5] ]
これは線形合同法*2(漸化式 )の単純な実装であるが、結果からも分かるように、周期は
に強く依存するため*3、大きな値
を用いることで長い周期の乱数を得る事ができる。しかしそれに応じて計算処理の膨大化の他、既知の様々な問題*4がある。M系列は
を Bitwise XOR とした時、次の高次線形漸化式で発生する 1 ビット数列を言い、線形合同法の欠点を克服する。
import Test.HUnit import System.IO import Data.Bits p :: Int p = 3 mseq :: Int -> Int mseq 0 = 1 mseq 1 = 0 mseq 2 = mseq 1 mseq n | p > q = (mseq (n - p) `xor` mseq (n - q)) :: Int where q = 1 invmseq :: [Int] -> [Int] invmseq [] = [] invmseq (x:xs) | x >= 0 = mseq x : invmseq xs isUniqueImpl :: [Int] -> [[Int]] -> Bool isUniqueImpl x (y:z) | x == y = False | otherwise = isUniqueImpl x z isUniqueImpl x y = [x] /= y isUnique' :: [[Int]] -> Bool isUnique' [] = True isUnique' [_] = True isUnique' (x:xs) | not (isUniqueImpl x xs) = False | otherwise = isUnique' xs shiftpPattern :: [Int] -> [[Int]] shiftpPattern [] = [] shiftpPattern xs | length xs >= p = take p xs : shiftpPattern (drop 1 xs) | otherwise = [] main :: IO (Counts, Int) main = runTestText (putTextToHandle stderr False) tests where x = invmseq [0 .. 8] shiftp = shiftpPattern x isunique = isUnique' $shiftp tests = TestList [ "mseq" ~: x ~?= [1, 0, 0, 1, 1, 1, 0, 1, 0], "shift pattern" ~: shiftp ~?= [[1, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1], [1, 1, 0], [1, 0, 1], [0, 1, 0]], "unique check" ~: isunique ~?= True ]
shiftp
が示しているように、先頭から 1 ビットずつずらした ビットの数列は、それぞれが他の数列と一切異なる数列、つまり
ビットで表現できるビットパターンを網羅している事が分かる。しかしそれは全てではなく、全てのビットパターンが 0 となる数列は発生されない*5。よって、M系列の周期
は
で求まる事が言える。
この時選ばれる と
の値は次の式が既約多項式となるようにして選ばれる。
次にこれまでで用いた
[※ 追記 もっと単純化できた...
-- 追記ここまで]
蛇足
有名なメルセンヌ・ツイスタ(MT)はこのM系列を発展させたものであり、Twisted General Feedback Shift Register(TGFSR) がはじめに発案された。これは、次の漸化式 によって発生する。
は Twister と呼ばれる
の元を要素とする
の行列である。TGFSR はM系列と同様
の最大周期を持つ、すなわちM系列よりも周期が長く、かつ高速な演算となるような
を選択できることから、M系列よりも優れる。MT はこの TGFSR を改良したものであり、次の漸化式
によって発生する。式
による最大周期が
である時、特に MT19937 と呼ばれる*7。