Représentation des entiers naturels¶

print(1+2*5**1+4*5**3)
print(1+1*2**2)
    

def convert(n,b,verbose=False):
    """retourne sous forme de tableau l'écriture en base b de  l'entier n écrit en base 10"""
    t = []
    if n==0:
        return [0]
    while n>0:
        quotient, reste = n//b,n%b
        if verbose:
            print("%s=%s*%s+%s"%(n,quotient,b,reste))
        t.append(reste)
        n = quotient
    #on renverse le tableau des restes successifs
    t.reverse()
    return t

#conversion en base 2
b = 2
for i in [0,7,34,128]:
    print("L'écriture en base %s de %s est %s"%(b,i,convert(i,b)))

#conversion en base 5
b = 5
for i in [0,7,34,128]:
    print("L'écriture en base %s de %s est %s"%(b,i,convert(i,b))) 

print() 
print("Détail de l'algorithme des divisions successives pour la conversion de 34 en base 2")
print() 
print(convert(34,2,verbose=True))

print()
print("Détail de l'algorithme des divisions successives pour la conversion de 34 en base 5")
print() 
print(convert(34,5,verbose=True))


          

def nbchiffres(n):
    """Retourne le nombre de chiffres dans l'écriture en base 10 d'un entier"""
    c = 1
    n = n//10
    while n>=1:
        n = n//10
        c += 1
    return c

for i in [0,9,22,99,100,999,1001]:
    print('Nombre de chiffres en base 10 de %s : %s'%(i,nbchiffres(i)))
    

def base5to10(n):
    """Retourne l'écriture en base 10 d’un entier entré par l’utilisateur en base 5"""
    #on récupère les chiffres sous forme de chaine
    chiffres = str(n)
    L = len(chiffres)
    decimal = 0
    for i in range(L):
        decimal += int(chiffres[L-1-i])*5**i
    return decimal

for i in [0,1,12,21,10,11,100,102]:
    print("%s en base 5 s'écrit %s en base 10"%(i,base5to10(i)))
    
        

def base5to10horner(n):
    """prend en argument un entier naturel n écrit en base 5
    et qui retourne son écriture en base 5.
    Meme principe que la fonction base5to10 mais moins de multiplications (algorith d'Horner)"""
    chiffres = str(n)  
    decimal = 0
    for c in chiffres:
        decimal = int(c) + decimal*5
    return decimal
    

for i in [0,1,12,21,10,11,100,102]:
    print("%s en base 5 s'écrit %s en base 10"%(i,base5to10horner(i)))

2**24

def convert(n,b,verbose=False):
    """retourne sous forme de tableau l'écriture en base b de  l'entier n écrit en base 10"""
    t = []
    if n==0:
        return [0]
    while n!=0:
        quotient, reste = n//b,n%b
        if verbose:
            print("%s=%s*%s+%s"%(n,quotient,b,reste))
        t.append(reste)
        n = quotient
    #on renverse le tableau des restes successifs
    t.reverse()
    return t

b=2
for i in [0,7,9,35,255,512,1025]:
    print("L'écriture en base %s de %s est %s"%(b,i,convert(i,b)))
    

#bin convertit un entier en base 2 (retourne une chaine)
help(bin)
a = bin(9)
print(a)
#int convertit une chaine en entier dans la base souhaitée
b = int(a,2)
print(b)

def len2b(n):
    """prend en argument un entier naturel n écrit en base 10
    et retourne la longueur de son écriture en  base 2
    Meme code que la fonction nbchiffres de l'exo 1 qui retournait le nombre de chiffres en base 10"""
    c = 1
    n = n//2
    while n>=1:
        n = n//2
        c += 1
    return c

for i in [0,7,8,31,32,255,256]:
    print("Nombre de chiffres en base 2 de %s : %s \n\
Vérification : bin(%s)=%s \n"%(i,len2b(i),i,bin(i)))
           

def len2bis(n):
    """Le nombre de chiffres de n en base 2 est l'exposant de la plus petite puissance de 2
    qui lui est strictement supérieure"""
    if n == 0: #cas particulier de 0 qui est le seul nombre commençant par 0
        return 1
    puissance = 1
    exposant = 0
    while puissance <= n:
        puissance *= 2
        exposant += 1
    return exposant

for i in [0,7,8,31,32,255,256]:
    print("Nombre de chiffres en base 2 de %s : %s \n\
Vérification : bin(%s)=%s \n"%(i,len2bis(i),i,bin(i)))

def base10to2(n):
    """prend en argument un entier naturel n écrit en base 10
    et qui retourne son écriture en base 2
    Même principe que la fonction convert présentée dans l'exo 1 sauf qu'on retourne
    un entier et non une liste"""
    k,a = 0,0
    while n>0:
        a = a+(n%2)*10**k
        k = k+1
        n = n//2
    return a

#conversion en base 2 avec bas10to2, vérification avec les exemples de l'exo 1
for i in [0,7,34,128]:
    print("L'écriture en base 2 de %s est %s"%(i,base10to2(i)))

def base10to2bis(n):
    '''Retourne le tableau des bits en base 2 du décimal n
    A connaitre par coeur pour le prochain DS'''
    t = [n%2]
    n = n//2
    while n > 0:
        t.append(n%2)
        n = n//2
    t.reverse()
    return t

#conversion en base 2 avec bas10to2, vérification avec les exemples de l'exo 1
for i in [0,7,34,128]:
    print("L'écriture en base 2 de %s est : "%i,base10to2bis(i))

def base10to2rec(n):
    if n <= 1:
        return str(n%2)
    return base10to2rec(n//2) + str(n%2)

#conversion en base 2 avec bas10to2, vérification avec les exemples de l'exo 1
for i in [0,7,34,128]:
    print("L'écriture en base 2 de %s est %s"%(i,base10to2rec(i)))

def base2to10(n):
    """prend en argument un entier naturel n écrit en base 2
    et qui retourne son écriture en base 2.
    Meme principe que la fonction base5to10 de l'exo 2"""
    chiffres = str(n)
    L = len(chiffres)
    decimal = 0
    for i in range(L):
        decimal += int(chiffres[L-1-i])*2**i
    return decimal
    

#conversion en base 2 avec bas10to2, vérification avec les exemples de l'exo 1
for i in [7,34,128]:
    print("L'écriture en base 2 de %s est %s"%(base10to2(i),base2to10(base10to2(i))))

def base2to10horner(n):
    """prend en argument un entier naturel n écrit en base 2
    et qui retourne son écriture en base 2.
    Meme principe que la fonction base2to10 mais moins de multiplications (algorith d'Horner)"""
    chiffres = str(n)  
    decimal = 0
    for c in chiffres:
        decimal = int(c) + decimal*2
    return decimal
    

#conversion en base 2 avec bas10to2, vérification avec les exemples de l'exo 1
for i in [7,34,128]:
    print("L'écriture en base 2 de %s est %s"%(base10to2(i),base2to10horner(base10to2(i))))

def puissance2dans(n):
    """Retourne la plus grande puissance de 2 inférieure ou égale à n"""
    p = 1
    while p <= n:
        p *= 2
    return p//2

def b10to2(n):
    """Retourne sous forme de chaine de caractères la représentation en binaire de 
    l'entier n en retranchant   successivement les plus grandes puissances de 2 que
    peut contenir l'entier variable"""
    p = puissance2dans(n)
    if n == 0:
        return '0'
    rep = ''
    while p > 0:
        if p <= n:
            rep = rep + '1'
            n = n - p
        else:
            rep = rep + '0'
        p //= 2
    return rep

#conversion en base 2 avec b10to2, vérification avec les exemples de l'exo 1
print('Algorithme 2, version itérative')
for i in [0,7,34,128]:
    print("L'écriture en base 2 de %s est %s"%(i,b10to2(i)))
    
def b10to2rec(n):
    """Conversion de base dix en base deux. Fonction récursive avec enveloppe"""
    
    def b10to2rec2(n, p):
        if p == 0:
            return ''#terminaison de la récursion
        elif p <= n:
            return '1' + b10to2rec2(n-p, p//2)
        else:
            return '0' + b10to2rec2(n, p//2)
    
    p2 = puissance2dans(n)
    return b10to2rec2(n, p2)
        
#conversion en base 2 avec b10to2rec, vérification avec les exemples de l'exo 1
print('Algorithme 2, version récursive')
for i in [0,7,34,128]:
    print("L'écriture en base 2 de %s est %s"%(i,b10to2rec(i)))

for i in [67,188]:
    print("L'écriture en base %s de %s est %s"%(b,i,base10to2(i)))
#on remarque que les écritures binaires de 67 et 188 sont complémentaires sur 8 bits
#c'est lié à 67+188=255

def base10to2V2(n):
    """prend en argument un entier naturel n écrit en base 10 et compris entre 0 et 255
    et  retourne son écriture en base 2 sous forme de chaine 
    en complétant par des 0 à gauche pour avoir huit bits exactement"""
    k,a = 0,0
    while n>0:
        a = a+(n%2)*10**k
        k = k+1
        n = n//2
    L = len(str(a))
    if L<8:
        return (8-L)*'0'+str(a)
    return str(a)

def complement(n):
    assert 0<=n<=255,'n doit être un entier entre 0 et 255'
    return base10to2V2(255-n)

for i in [7,34,127,128,256]:
    print("L'écriture en base 2 de %s est %s \n\
et celle de son complément binaire est %s"%(i,base10to2(i),complement(i)))

#exo 10 Chapitre codage des nombres
#exponentiation rapide

import time

def timetest(fonction):
    """Décorateur pour le calcul du temps d'exécution"""
    def fonction_modifiee(*args,**kargs):
        tps_avant = time.time()
        ret = fonction(*args,**kargs)
        tps_apres = time.time()
        print("Le temps d'exécution de la fonction est de {:10.3e} s"
              .format(tps_apres-tps_avant))
        return ret
    return fonction_modifiee

@timetest
def expo_naive(a,n):
    """exponentiation naive version itérative"""
    p = 1
    for i in range(n):
        p = p*a
    return p
    
@timetest
def expo_rapide_rec(a,n):
    """exponentiation rapide version récursive"""
    if n==0:
        return 1
    elif n%2==0:
        return expo_rapide_rec(a**2,n//2)
    return a*expo_rapide_rec(a**2,n//2)

@timetest
def expo_rapide_iter(a,n):
    """exponentiation rapide version itérative"""
    m,p,r = n,a,1
    while m>0:
        if m%2==1:
            r = p*r
        p = p*p
        m = m//2
    return r

print(expo_naive(2,1000))
print(expo_rapide_iter(2,1000))
print(expo_rapide_rec(2,1000))

def base10tob(n,b):
    """prend en argument un entier naturel n écrit en base 10
    et qui retourne son écriture en base b sous forme de liste.
    Même principe que la fonction base10to2 mais ici on retourne une liste
    pour ne plus etre géné par la représentation en base >10"""
    t = []
    if n==0:
        return [0]
    while n>0:
        t.append(n%b)
        n = n//b
    #on renverse la liste des chiffres puisqu'on a d'abord obtenu les chiffres de poids faible
    t.reverse()
    return t

#conversion en base 5, on reprend l'exemple de l'exo 1
b = 5
for i in [0,7,34,128]:
    print("L'écriture en base %s de %s est : "%(b,i),base10tob(i,b))

#conversion en base 16
b = 16
for i in [0,7,34,128]:
    print("L'écriture en base %s de %s est : "%(b,i),base10tob(i,b))

for i in [17,35,171,255,865]:
    print("L'écriture hexadécimale de %s est %s"%(i,hex(i)))

def base16to10(chaine):
    """Retourne l'écriture en base 10 sous forme d'entier d'un entier dont on passe
    en paramètre la chaine de représentation en base 16 sous la forme '0x2A'"""
    #on transforme la chaine en majuscules
    chaine = chaine.upper()
    #on élimine les deux premiers caractères '0X' à gauche s'ils existent
    if chaine[:2]=='0X':
        chaine = chaine[2:]
    L = len(chaine)
    decimal = 0
    #dictionnaire des chiffres en base 16
    dico = {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'A':10,'B':11,'C':12,'D':13,'E':14,'F':15}
    for i in range(L):
        decimal += dico[chaine[L-1-i]]*16**i
    return decimal

for i in ['0x0','0x3ae','0xFFF','0x6aF']:
    r= base16to10(i)
    print("L'écriture décimale de %s est %s"%(i,r),'\nVérification : %s'%hex(r))
    
    

def base10to16(n):
    """retourne la liste des chiffres de l'écriture en base 16 
    (ou une cha\^ine de caractères) d'un entier n en respectant la nomenclature ci-dessus.
    On pourra utiliser un dictionnaire pour la traduction des chiffres"""
    #liste des chiffres en base 16
    t = []
    #on peut se passer d'un dictionnaire
    chiffre = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']
    if n==0:
        return ['0']
    while n>0:
        t.append(chiffre[n%16])
        n = n//16
    #on renverse la liste des chiffres puisqu'on a d'abord obtenu les chiffres de poids faible
    t.reverse()
    return t

def base10to16V2(n):
    """quitte à retourner une liste de caractères autant retourner une chaine
    de représentation hexadécimale à la manière de la fonction hex de  Python"""
    chaine = ''
    chiffre = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']
    if n==0:
        return '0x0'
    while n>0:
        chaine = chiffre[n%16]+chaine
        n = n//16
    return '0x'+chaine

for i in [0,17,35,171,255,865]:
    print("L'écriture hexadécimale de %s est %s"%(i,base10to16V2(i)),'ou :\n',base10to16(i),'\n')


    

def mac_from_hexa_2_bin(m):
    """Traduit une MAC adresse en hexadécimal de type A1-FB-64-3B-AB-FF
    sous la forme d'une représentation binaire"""
    #tableau qui contiendra les écritures binaires successives
    t=[]
    for c in m.split('-'):
        #expliquer la ligne suivante
        t.append(str(base10to2(base16to10(c))))
    return '-'.join(t)

mac= 'A1-FB-64-3B-AB-FF'
print("L'écriture en binaire de la MAC adresse %s est :\n"%mac,mac_from_hexa_2_bin('A1-FB-64-3B-AB-FF'))

def base10to16V3(n):
    """redéfinition de base10to16V2, prend en en entrée un entier entre 0 et 255
    et retourne sa représentation hexadécimale sous la forme d'une chaine de 2 caractères"""
    v = base10to16V2(n)[2:]
    if len(v)==1:
        return '0'+v
    return v
    

def rgb2html(r,g,b):
    """prend en entrée 3 entiers R,G et B entre 0 et 255 
    et retourne une chaine de caractères correspondant à la notation HTML de la couleur (R,G,B)"""
    chaine = '#'
    for i in [r,g,b]:
        chaine += base10to16V3(i)
    return chaine

def html2rgb(chaine):
    """réciproque de la précédente"""
    rgb = []
    for i in range(1,len(chaine)-1,2):
        rgb.append(base16to10(chaine[i:i+2]))
    return rgb

r,g,b = 255,0,0
html=rgb2html(r,g,b)
print("La notation HTML de la couleur (%s,%s,%s) est %s"%(r,g,b,html))
print("La représentation (R,G,B) de la couleur de notation HTML %s est : \n"%html,html2rgb(html))

#vérification avec Python
print(bin(3*4+2))
print(bin(11*16+10))

for i in range(64):
    print(i,'->',repr(2**i-1))
#Une version 32 bits de Python est installée sur ma machine
#2**31-1 est alors le plus grand entier représentable sur un mot de 32 bits
#au-delà les entiers sont réprésentés par Python2 sur plus d'un mot, ce sont des entiers longs (suffixe L)
#2**31-1 apparait ci-dessous comme un entier long car Python calcule d'abord 2**31 qui est un entier long
#Python3 n'a plus de type entier long

import sys
#plus grand entier signé représenté sur un mot machine
sys.maxsize,2**31-1

#on utilise les fonctions  complement et base10to2V2 de l'exercice 9

def base10to2V3(n):
    """prend en argument un entier naturel n écrit en base 10 et compris entre -128 et 127
    et  retourne son écriture en base 2 en complément à deux sous forme de chaine 
    en complétant par des 0 à gauche pour avoir huit bits exactement"""
    assert -128<=n<=127,'Erreur de débordement, n doit être un entier compris entre -128 et 127'
    if 0<n<=127:
        return base10to2V2(n)
    elif -128<=n<0:
        return base10to2V2(n+256)
    return '0'*8



for i in [54,-1,-2,127,-127,-128,128]:
    print("La représentation binaire de %s en complément à deux\
 est %s \n"%(i,base10to2V3(i)))

def oppose_complement2(n):
    """Retourne l'écriture binaire en complément à 2 de l'opposé d'un entier compris entre -127 et 127
    ou un message d'erreur s'il y a débordement"""
    assert -127<=n<=127,'Erreur de débordement, n doit être un entier compris entre -127 et 127'
    if 0<n<=127:
        return base10to2V2(int('0b'+complement(n),2)+1)
    elif -127<=n<0:
        return base10to2V2(int('0b'+complement(n+256),2)+1)
    return '0'*8

for i in [4,100,-8,1,127,-127,-128]:
    if i<0:
        j = i+256
    else:
        j = i
    print "La représentation binaire de %s est %s \n\
et la représentation de son opposé %s en complément à deux est\
: %s\n"%(i,base10to2V2(j),-i,oppose_complement2(i))

a = 1.
b = 2.
i = 1
while i<11:
    a = b
    b = b*a
    c = 2**(2**i)
    print(type(b),b,' ; ',type(c),c)
    i += 1

2.**(2**10)

2**(2**10)

def base10to2(n,digit):
    """Ecrit un développement en base 2 d'un flottant n.
    On calcule d'abord le développement en binaire de  la partie entière
    puis celui de la partie fractionnaire.
    Retourne un flottant qu'il faut bien interpréter comme une représentation en binaire"""
    i = 0
    #partie entière de n
    quotient = int(n)
    #partie entière en binaire
    partentbin = 0
    while quotient>0:
        bit = quotient%2
        quotient = quotient//2
        partentbin = partentbin+bit*10**i
        i = i+1
    #partie fractionnaire en écriture décimale
    partfracdec = n-int(n)
    partfracbin = 0
    i = 0
    lbitspartfracbin = []
    while partfracdec!=0 and i<digit:
        partfracbin = partfracbin*10
        bit = int(partfracdec*2)
        partfracbin += bit
        lbitspartfracbin.append(bit)
        #print(partfracdec)
        partfracdec = 2*partfracdec-bit
        i+=1
    print('Nombre de bits de la partie fractionnaire  en binaire réellement calculés ; ',i)
    print('Liste des bits de la partie fractionnaire  en binaire réellement calculés : \n',lbitspartfracbin)
    print('La liste des bits affichés est réduite à 20 bits après la virgule au maximum : \n')
    return(partentbin+partfracbin/10.**i)
        
        
        

n = 0.2
d = 56
print('Développement en base 2 de %s : %s'%(n,base10to2(n,d)))

"""On considère un codage des flottants sur $6$ bits avec $1$ bit de signe $s$,  l'exposant $e$ codé sur $3$ bits et la mantisse  $m$ codée sur $2$ bits."""

def flottants(e,m):
    """affiche tous les flottants positifs dont l'exposant est codé sur e bits et 
    la mantisse sur m bits"""
    decalage = 2**(e-1)-1
    for i in range(2**(e)):
        for j in range(2**(m)):
            if i==7 and j>0:
                print('e = %s et m=%s : NAN'%(i,j))
            elif i==7 and j==0:
                print('e = %s et m=%s : infini'%(i,j))
            elif i==0 and j>0:
                print('e = %s et m=%s, flottant dénormalisé : %s'%(i,j,2**(1-decalage)*(j/2**m)))
            elif i==0 and j==0:
                print('e = %s et m=%s : 0'%(i,j))
            elif i==7 and j==0:
                print('e = %s et m=%s : infini'%(i,j))
            else:
                print('e = %s et m=%s : %s'%(i,j,2**(i-decalage)*(1+j/2**m)))

e = 3
m = 2
flottants(e,m)

import sys
#calcul du plus grand flottant au format double
a = 2.**1023
b = a/2
for i in range(1,53):
    a,b = a+b,b/2
print('le plus grand flottant au format double est %s'%a)
#affichage du plus petit flottant normalisé au format double
print( 'le plus petit flottant normalisé au format double est :',2**(-1022))
print( 'le plus petit flottant dénormalisé au format double est 2**(-1074) : ',2**(-1074))
print( ' 2**(-1075) : ',2**(-1075) )
print( 'Vérification : \n',sys.float_info)

def mystere():
    x = 1.
    y = x+1.
    i = 0
    while (y-x == 1.):
        i += 1
        x = x*2.
        y = x+1.
    print(i,x,y)

mystere()

2.**53-1==2.**53,2.**53 == 2.**53+1,2.**53 == 2.**53+2

2.**53

2.**53+1

2.**53+2

def somme1(n):
    s = 0.
    for i in range(1,n+1):
        s += 1./i**4
    return s


def somme2(n):
    s = 0.
    for i in range(n+1,0,-1):
        s += 1./i**4
    return s


print(somme1(100000))
print(somme2(100000))

%%python
#Python2 ne retourne pas les memes resultats
def somme1(n):
    s = 0.
    for i in range(1,n+1):
        s += 1./i**4
    return s


def somme2(n):
    s = 0.
    for i in range(n+1,0,-1):
        s += 1./i**4
    return s


print(somme1(100000))
print(somme2(100000))

#fonction
def recurrence(n):
    u0 = 1./3
    u1 = 0
    for i in range(n) :
        u1 = 4*u0 - 1.
        u0 = u1
    return u1

#programme principal
print('4/3 - 1 == 1/3 est',4./3 - 1 == 1./3)
for i in range(1,50):
    res = recurrence(i)
    print('recurrence(%s)=%.8f'%(i,res))

"""Fonctions booléennes"""
#l'opérateur a%2 retourne le reste de la division euclidienne de a par 2
#x et y sont des entiers entre 0 et 1 

def ou(x,y):
    """ou inclusif """
    return (x+y+x*y)%2
def et(x,y):
    """et"""
    return x*y

def xou(x,y):
    """ou exclusif"""
    return (x+y)%2
def non(x):
    """non"""
    return 1-x