evalPRNG/calculeStopTime.py

   1 import random as rn
   2 import numpy as np
   3 from math import *
   4
   5
   6 def bin(elem,n):
   7     """Convertit un nombre en binaire"""
   8     q = -1
   9     res =[0 for i in range(n)]
  10     i = 1
  11     while q != 0:
  12         q = elem // 2
  13         r = elem % 2
  14         res[n-i] =  r
  15         elem = q
  16         i+=1
  17     return res
  18
  19 def dec(ch,n):
  20     l = len(ch)
  21     acc = 0
  22     for i in range(l):
  23         if ch[i]==1 :
  24             acc = acc + 2**(n-i-1)
  25     return acc
  26
  27
  28 def MarkovMatrixUnPas(fbin,n,p2n,lp2nm1):
  29     MM = np.zeros(p2n*p2n).reshape((p2n,p2n))
  30     # diagonal
  31     for i in lp2nm1 :
  32         ib = bin(i,n)
  33         MM[i,i] += 0.5
  34         image = fbin[tuple(ib)]
  35         for j in range(n):
  36             ipb =[_ for _ in ib]
  37             ipb[j] = image[j]
  38             MM[i, dec(ipb,n)] +=float(1)/(2*n)
  39     print MM
  40     return MM
  41
  42 """
  43 def MarkovMatrixUnPas(fbin,n,p2n,lp2nm1):
  44     MM = np.zeros(p2n*p2n).reshape((p2n,p2n))
  45     # diagonal
  46     for i in lp2nm1 :
  47         ib = bin(i,n)
  48         #MM[i,i] += 0.5
  49         image = fbin[tuple(ib)]
  50         for j in range(n):
  51             ipb =[_ for _ in ib]
  52             ipb[j] = image[j]
  53             MM[i, dec(ipb,n)] +=float(1)/(n)
  54     return MM
  55
  56
  57
  58
  59 """
  60 def MarkovMatrixSaut(fbin,n,p2n,lp2nm1):
  61     MM = np.zeros(p2n*p2n).reshape((p2n,p2n))
  62     # diagonal
  63     for i in lp2nm1 :
  64         ib = bin(i,n)
  65         MM[i,i] += 0.5
  66         image = fbin[tuple(ib)]
  67         for j in lp2nm1:
  68             st = bin(j,n)
  69             ipb =[_ for _ in ib]
  70             for k in range(n):
  71                 if st[k] == 1 :
  72                     ipb[k] = image[k]
  73             MM[i, dec(ipb,n)] +=float(1)/(2*2**n)
  74     return MM
  75 """
  76
  77 def MarkovMatrixSaut(fbin,n,p2n,lp2nm1):
  78     MM = np.zeros(p2n*p2n).reshape((p2n,p2n))
  79     # diagonal
  80     for i in lp2nm1 :
  81         ib = bin(i,n)
  82         #MM[i,i] += 0.5
  83         image = fbin[tuple(ib)]
  84         for j in lp2nm1:
  85             st = bin(j,n)
  86             ipb =[_ for _ in ib]
  87             for k in range(n):
  88                 if st[k] == 1 :
  89                     ipb[k] = image[k]
  90             MM[i, dec(ipb,n)] +=float(1)/(2**n)
  91     return MM
  92
  93
  94 """
  95 """
  96
  97     # f is the binary function
  98     # b is the number to iterate
  99     # x0 is the intial binary conf
 100     xp = [e for e in x]
 101     #print "************************"
 102     #print "x0     ", xp
 103     for j in xrange(b):
 104         if rn.randint(0,1) == 1:
 105
 106             st = rn.randint(0,n-1)
 107             #print "x["+str(st)+"]="+str(xp[st])+"->"+str(image[st])
 108             xp[st] = image[st]
 109         #print "xp     ",xp
 110     return xp
 111 """
 112
 113
 114 ## n'est pas un circuit hmiltonien
 115 lf= []
 116 #lf +=[ [13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]] #4
 117 #lf+=[[29, 22, 21, 24, 31, 30, 27, 26, 7, 23, 5, 28, 3, 19, 25, 17, 13, 12, 9, 8, 15, 2, 1, 10, 6, 14, 4, 20, 11, 18, 0, 16]]
 118
 119 #lf += [[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4],[29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0,16]] # essai des 2 elements a 5
 120
 121 lf +=[
 122     [29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0, 16],#sylvain 1
 123     [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4],#sylvain 2
 124     [29, 22, 21, 24, 31, 30, 27, 26, 7, 23, 5, 28, 3, 19, 25, 17, 13, 12, 9, 8, 15, 2, 1, 10, 6, 14, 4, 20, 11, 18, 0, 16], #mini avec 7
 125     [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]] #5
 126
 127
 128
 129
 130 lf +=  [[55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]] #6
 131
 132 """
 133 lf += [[111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118, 117, 96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66, 101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, 26, 18, 89, 25, 87, 30, 23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21, 68, 7, 6, 65, 1]] #7
 134 lf += [[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]]#8
 135
 136 """
 137
 138 # 14 = (1,1,1,0) = f(0,0,0,0)
 139 #  6 = (0,1,1,0) = f(0,0,0,1)
 140 #....
 141 # 8  = (1,0,0,0) = f(1,1,1,1)
 142
 143
 144 def traite_f(f):
 145     n = int(log(len(f))/log(2))
 146     #nbre d'elements
 147     p2n = int(pow(2,n))
 148     lp2nm1 = range(p2n)
 149     # pour eviter de le calculer a chaque fois
 150     # fbin est la fonction (representee comme un dico)
 151     # qui au tuple binaire (x3,x2,x1,x0) associe
 152     # le nombre f(x3,x2,x1,x0)
 153     fbin={}
 154     for j in range(len(f)):
 155         fbin[tuple(bin(j,n))] = bin(f[j],n)
 156
 157     MM = MarkovMatrixUnPas(fbin,n,p2n,lp2nm1)
 158     M = np.zeros(p2n*p2n).reshape((p2n,p2n))
 159     np.copyto(M,MM)
 160
 161     MMs = MarkovMatrixSaut(fbin,n,p2n,lp2nm1)
 162     Ms = np.zeros(p2n*p2n).reshape((p2n,p2n))
 163     np.copyto(Ms,MMs)
 164
 165
 166
 167     error = 1
 168     cpt = 2
 169     while error > dev :
 170         M = np.dot(M,MM)
 171         error =max([sqrt(sum([(M[i,j] - float(1)/p2n)**2  for i in range(p2n)])) for j in range(p2n)])
 172         #print cpt, error, M
 173         cpt +=1
 174
 175
 176     error = 1
 177     cpts = 2
 178     while error > dev :
 179         if n==4 and cpts==2:
 180             print Ms
 181         Ms = np.dot(Ms,MMs)
 182         error =max([sqrt(sum([(Ms[i,j] - float(1)/p2n)**2  for i in range(p2n)])) for j in range(p2n)])
 183         #print cpt, error, M
 184         cpts +=1
 185
 186
 187
 188     return n, cpt-1, cpts-1
 189
 190
 191
 192 for f in lf:
 193     dev = 1E-12
 194     n,cpt1,cpt2 = traite_f(f)
 195     print f, n,cpt1,cpt2
 196     print 8*n*n + 4*n*log(n+1)#,8*n*n + (n+2)*(log(n)+2)
 197     print "Pour "+str(n)+" bits et pour eps="+str(dev)+", appels a rand moy pr 1 bit genere.",
 198     print "En marchant:", cpt1*log(n)/(log(2)*n),
 199     print "En sautant:", cpt2
 200
 201