experiments/prng.py

   1 from random import *
   2 import numpy as np
   3 from time import *
   4 from math import *
   5 from random import *
   6
   7
   8
   9 # let elem be a integer.
  10 # This function returns the binary value of elem
  11 # expressed on n bits.
  12 def bin(elem,n):
  13     q = -1
  14     res =[0 for i in range(n)]
  15     i = 1
  16     while q != 0:
  17         q = elem // 2
  18         r = elem % 2
  19         res[n-i] =  r
  20         elem = q
  21         i+=1
  22     return res
  23
  24
  25 # let ch be a binary number expressed on n bits.
  26 # This function returns the decimal value of this
  27 # binary number.
  28 def dec(ch,n):
  29     l = len(ch)
  30     acc = 0
  31     for i in range(l):
  32         if ch[i]==1:
  33             acc = acc + 2**(n-i-1)
  34     return acc
  35
  36
  37
  38 # Let be given a function f defined as a list of size 2^n
  39 # that contains the images f[x] of the element at index x
  40 # where x is an index, 0 <= x <= 2^n-1.
  41 # Let X be an index, 0 <= x <= 2^n-1, and k be an index, 0 <= k <= n-1,
  42 # this function returns the map fp such that fp[x][k] = y
  43 # where y is x except at bit k where the value is the bit f[x][k].
  44 def f_to_map(f):
  45     # size of
  46     lf = len(f)
  47     # number of bits
  48     n= int(log(len(f))/log(2))
  49     # fp is the returned two dimensional array
  50     fp = np.zeros((2**n,n))
  51     for i in xrange(lf):
  52         ib = bin(i,n)
  53         imgib = bin(f[i],n)
  54         for j in xrange(n):
  55             ibp = [_ for _ in ib]
  56             ibp[j] = imgib[j]
  57             fp[i,j] = dec(ibp,n)
  58     return fp
  59
  60
  61
  62 # let fmap be a function expressed as a map.
  63 # let n be the largest value returned by the prng (i.e. the number of bits)
  64 # let randf be a prng that can return integer from 0 to n-1
  65 # let b be the number of iterations
  66 # le x0 be a integer value such that 0 <= x0 <= 2^n-1
  67 def ourPrng(fmap,n,randf,b,x0):
  68     x = x0
  69     for _ in xrange(b):
  70         s = randf(0,n-1)
  71         x = fmap[x][s]
  72     return x
  73
  74
  75
  76 # Let be given a function f defined as a list of size N
  77 # that contains the images f[x] of the element at index x and
  78 # let b be the number of iterations that has to be executed and
  79 # rand be a prng that can randomly find integer between two bounds.
  80 # This function cumputes the NxN array successors such that
  81 # successors[i][j] is the number of times i has been followed by j
  82 # where 0 <= i <= N-1 and 0 <= j <= N-1.
  83 def testPrng(f,rand,b):
  84     lf = len(f)
  85     successors=[[0 for _ in range(lf)] for _ in range(lf)]
  86     x0 = 0
  87     fp = f_to_map(f)
  88     n= int(log(len(f))/log(2))
  89     for _ in range(lf*lf*1000):
  90         old_x = x0
  91         x0 = int(ourPrng(fp,n,rand,b,x0))
  92         successors[old_x][x0] +=1
  93     return successors
  94
  95 def main():
  96     l1 = testPrng([13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8],randint,32)
  97     print l1
  98     l2 = testPrng([55, 60, 45, 56, 58, 62, 61, 40, 53, 38, 52, 54, 35, 51, 33, 49, 39, 14, 47, 46, 59, 43, 57, 44, 37, 6, 36, 4, 3, 50, 1, 48, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 12, 29, 8, 10, 42, 41, 0, 15, 2, 7, 5, 11, 34, 9, 32],randint,49)
  99     print l2
 100     l3 = testPrng([223, 250, 249, 254, 187, 234, 241, 252, 183, 230, 229, 180, 227, 178, 240, 248, 237, 236, 253, 172, 251, 238, 201, 224, 247, 166, 165, 244, 163, 242, 161, 225, 215, 220, 205, 216, 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 142, 207, 206, 139, 203, 193, 136, 135, 196, 199, 132, 194, 130, 129, 200, 159, 186, 185, 190, 59, 170, 177, 188, 191, 246, 245, 52, 243, 50, 176, 184, 173, 46, 189, 174, 235, 42, 233, 232, 231, 38, 37, 228, 35, 226, 33, 168, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, 145, 175, 14, 143, 204, 11, 202, 169, 8, 7, 198, 197, 4, 195, 2, 1, 192, 255, 124, 109, 120, 107, 126, 125, 112, 103, 114, 116, 100, 123, 98, 121, 113, 79, 106, 111, 110, 75, 122, 97, 108, 71, 118, 117, 68, 115, 66, 96, 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 74, 78, 105, 64, 69, 102, 101, 70, 99, 67, 73, 65, 55, 60, 45, 56, 51, 62, 61, 48, 119, 182, 181, 53, 179, 54, 57, 49, 15, 44, 47, 40, 171, 58, 9, 32, 167, 6, 5, 164, 3, 162, 41, 160, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 140, 43, 138, 137, 12, 39, 134, 133, 36, 131, 34, 0, 128],randint,75)
 101     print l3
 102
 103
 104 if __name__ == "__main__":
 105     main()
 106
 107
 108