Advertisement
Guest User

mauers tests

a guest
Apr 17th, 2014
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
F# 5.11 KB | None | 0 0
  1.  
  2. let linearGenerator(seed: int) =
  3.     let a = 16807;
  4.     let m = int (System.Math.Pow(2.0, 31.0) - 1.0);
  5.     let rec count(liczba: int, wynik: int) =
  6.         if liczba=0 then wynik else count((liczba-liczba%10)/10, wynik+1);
  7.     let index = count(m, 0);
  8.     let rec generate(seedi: int, iter: int) =
  9.         if iter=index then seedi else generate((a*seedi)%m, iter+1);
  10.     generate(seed, 0);
  11.  
  12. let toBinary(value: int) =
  13.     let rec binary(vali: int, lista: List<int>) =
  14.         if vali=0 then lista else binary((vali-vali%2)/2, vali%2::lista)
  15.     binary(value, [])
  16.  
  17. let addZero(listA: List<int>, max:int)=
  18.     if listA.Length < max then
  19.         [ for i in 1 .. (max-listA.Length) -> 0 ] @ listA
  20.     else listA
  21.  
  22. let cutter(n: int, list: List<_>) =
  23.     let firstList = list |> Seq.take n |> Seq.toList
  24.     let secondList = list |> Seq.skip n |> Seq.toList
  25.     [|firstList; secondList|]
  26.  
  27. let splitList(lista: List<int>, cut: int) =
  28.     let rec split(result: List<List<int>>, value: List<int>) =
  29.         if value.Length=0 then List.rev(result) elif value.Length<cut then value::result else split(cutter(cut, value).[0]::result, cutter(cut, value).[1])
  30.     split([], lista)
  31.  
  32. let possiblitiesList(num: int) =
  33.     let rec pList(result: List<List<int>>, number: int) =
  34.         if number<0 then result else pList(addZero(toBinary(number), num)::result, number-1)
  35.     pList([], (System.Math.Pow(2.0, num|>float)-1.0)|>int)
  36.  
  37. let expectedValue(L: int) =
  38.     match L with
  39.         | 1 -> 0.7326495;
  40.         | 2 -> 1.5374383;
  41.         | 3 -> 2.4016068;
  42.         | 4 -> 3.3112247;
  43.         | 5 -> 4.2534266;
  44.         | 6 -> 5.2177052;
  45.         | 7 -> 6.1962507;
  46.         | 8 -> 7.1836656;
  47.         | 9 -> 8.1764248;
  48.         | 10 -> 9.1723243;
  49.         | 11 -> 10.170032;
  50.         | 12 -> 11.168765;
  51.         | 13 -> 12.168070;
  52.         | 14 -> 13.167693;
  53.         | 15 -> 14.167488;
  54.         | 16 -> 15.167379;
  55.         | _ -> 0.0;
  56.  
  57. let variance(L: int) =
  58.     match L with
  59.         | 1 -> 0.690;
  60.         | 2 -> 1.338;
  61.         | 3 -> 1.901;
  62.         | 4 -> 2.358;
  63.         | 5 -> 2.705;
  64.         | 6 -> 2.954;
  65.         | 7 -> 3.125;
  66.         | 8 -> 3.238;
  67.         | 9 -> 3.311;
  68.         | 10 -> 3.356;
  69.         | 11 -> 3.384;
  70.         | 12 -> 3.401;
  71.         | 13 -> 3.410;
  72.         | 14 -> 3.416;
  73.         | 15 -> 3.419;
  74.         | 16 -> 3.421;
  75.         | _ -> 0.0;
  76.  
  77. let midpoint(funkcja:float->float,a:float,b:float,n:int)=
  78.     let h = (b-a)/((float)n)
  79.     let rec LiczCiag(funkcja:float->float,poprzedni:float,a:float,h:float,iter:int,n:int)=
  80.         if iter < n then
  81.             let mid =  poprzedni+ h*(funkcja(a+(h/2.0)+((float )iter*h)))
  82.             LiczCiag(funkcja,mid,a,h,iter+1,n)
  83.         else
  84.             poprzedni
  85.     let ciag = LiczCiag(funkcja,0.0,a,h,1,n)
  86.     ciag
  87.  
  88. let erfc(limit: float) =
  89.     let funk(x:float) = exp(-(x*x))
  90.     let funk2(x:float) = (1.0/System.Math.Pow(x,2.0))*(funk(1.0/x))
  91.     (2.0/System.Math.Sqrt(System.Math.PI))*midpoint(funk2,0.0,1.0/limit,1000)
  92.  
  93.  
  94. let mauersTester(L: int, Q: int, e: int) =
  95.     let mutable eBin = toBinary(e);
  96.     if not(eBin.Length%L=0) then eBin <- addZero(eBin, eBin.Length+(eBin.Length%L))
  97.     let splittedList = splitList(eBin, L);
  98.     let cutted = cutter(Q, splittedList);
  99.     let initSegment = cutted.[0];
  100.     let testSegment = cutted.[1];
  101.     let possibleValues = possiblitiesList(L);
  102.     let positionArray = Array.zeroCreate(possibleValues.Length);
  103.     let rec fillPositionArray(pList: List<List<int>>, iter: int, pos: int) =
  104.         if pList.Length=0 then pList
  105.         else if iter=possibleValues.Length then fillPositionArray(pList.Tail, 0, pos+1)
  106.              else if possibleValues.[iter] = pList.Head
  107.                   then positionArray.[iter] <- pos;
  108.                        fillPositionArray(pList.Tail, 0, pos+1);  
  109.                   else fillPositionArray(pList, iter+1, pos)
  110.     let l = fillPositionArray(initSegment, 0, 1);
  111.     let sum = ref 0.0;
  112.     let rec fillPositionArraySum(pList: List<List<int>>, iter: int, pos: int) =
  113.         if pList.Length=0 then pList
  114.         else if iter=possibleValues.Length then fillPositionArraySum(pList.Tail, 0, pos+1)
  115.              else if possibleValues.[iter] = pList.Head
  116.                   then sum := sum.Value + System.Math.Log(((pos+Q)-positionArray.[iter])|>float, 2.0);
  117.                        positionArray.[iter] <- pos+Q;
  118.                        fillPositionArraySum(pList.Tail, 0, pos+1);  
  119.                   else fillPositionArraySum(pList, iter+1, pos)
  120.     let s = fillPositionArraySum(testSegment, 0, 1);
  121.     let funk = sum.Value/(testSegment.Length|>float)
  122.     let sigma = System.Math.Sqrt(variance(L));
  123.     let limit = System.Math.Abs((funk-expectedValue(L))/(System.Math.Sqrt(2.0)*sigma))
  124.     erfc(limit);
  125.  
  126.    
  127. let mauersTest(number : int, bits: int, testSize: int) =
  128.     if mauersTester(bits, testSize, number)>0.01 then true else false;
  129.  
  130. let makeTests =
  131.     for i = 1 to 100 do printfn "%b" (mauersTest(linearGenerator(System.DateTime.Now.Millisecond),2, 4))
  132.  
  133.  
  134. (* Liczenie dla danych z książki
  135. let testC = mauersTester(2, 4, 370519)
  136. *)
  137.  
  138. printfn "%A" makeTests
  139.  
  140. System.Console.ReadKey(true);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement