Jeudi 21 Juillet 2005
[Python] - Math & Python
Aujourd'hui, grand coup de nettoyage dans mon /home. Je me retrouve avec des bouts de scripts python qui en intéresseront sûrement certains. Malheureusement pour d'autres, je passe la plus part de mon temps à implanter des algorithmes mathématiques en Python, donc il s'agit de petit trucs mathématique pas forcement utiles.
Conversion de base
Il peut être utile de convertir un nombre d'une base numérique vers une autre. Or il n'existe pas de fonction prévu à cet effet en Python hormis la fonction int capable de convertir un nombre de n'importe quel base (entre 2 et 32) vers 10. Cependant pour convertir dans une autre base il faut le faire à la main. En partant de la base 10, l'on peut facilement ce rendre dans les autres bases.
Explication mathématique
Un nombre dans une base s'écrit comme une somme de termes de la forme ab^c. Avec a une valeur en base 10 inférieure à la base. b la valeur de la base et c un exposant qui varie. Par exemple, 7 en binaire s'écrit 1 * 2 ^ 2 + 1 * 2 ^ 1 + 1 * 2 ^ 0 = 4 + 2 + 1. C'est ainsi qu'a partir de divisions l'on peut trouver l'écriture dans n'importe quel base d'un nombre.
from string import lowercase
def base_convert(number,frombase,tobase):
assert isinstance(number,str)
assert isinstance(frombase,int)
assert isinstance(tobase,int)
assert 2 <= frombase <= 36
assert 2 <= tobase <= 36
if frombase == tobase:
return number
# on met en base 10
base10 = int(number,frombase)
if tobase == 10:
return str(base10)
else:
# on met dans la nouvelle base
i = 0
while tobase ** (i + 1) <= base10:
i += 1
newbase = []
while i >= 0:
j = 0
while ((j+1) * tobase ** i <= base10) and (j < (tobase - 1)):
j += 1
base10 = base10 - j * (tobase ** i)
if j < 10:
newbase.append(str(j))
else:
newbase.append(lowercase[j - 10])
i -= 1
return "".join(newbase)
Cos et sin sans math
Cela ne sert à rien, mais voici comment obtenir des valeurs corrects de cos et sin sans la librairie math :
e = 2.7182818284590451 def cos(x): return (e ** (1j * x)).real def sin(x): return (e ** (1j * x)).imag
Petit rappels mathématiques.
Un nombre complexe d'argument x est définit tel que Z = exp(j * x) = cos(x) + isin(x). Sa partie entière est donc égale à cos(x) et sa partie imaginaire égale à sin(x).
Valeur de pi
Vous vous êtes toujours demandé comment l'on calculait la valeur de Pi avec des milliers de décimales. C'est en fait quelque chose de fort simple et en voici une méthode. Je ne dis pas que c'est la meilleur et les résultats donnés ici sont loin d'être bon du fait de l'imprécision des nombres flottants de python (Il faudrait utiliser les Decimal) mais c'est un exemple sympa qui comporte sûrement une petite erreur...
from future import division
size = 1000
nbhit = 0
nbgood = 0
for x in xrange(size + 1):
for y in xrange(size + 1):
nbhit += 1
if ((size / 2 - x) ** 2 + (size / 2 - y ) ** 2) <= (size / 2) ** 2:
nbgood += 1
print nbgood / nbhit * 4
Explication mathématique
L''air d'un cercle est égale à Pi produit de son rayon au carré. Donc un cercle inscrit dans un carré couvre une aire de Pi * r ** 2 alors que le carré a une air de 4r**2. On obtient donc un ratio entre les deux airs égale à Pi / 4.
On peut donc calculer Pi si l'on connaît le ratio des airs.
Produit cartésien
Un produit cartésien donne à partir de plusieurs liste toutes les combinaisons possibles avec les valeurs.
Le plus couramment c'est utilisé pour parcourir un tableau à plusieurs dimension et cela donne quelque chose très basique comme cela :
for x in range(10):
for y in range(10):
for z in range(10):
print x,y,z
Cependant on se rend vite compte que c'est extrêmement lourd. L'on peut simplifier l'expression avec une liste :
for x,y,z in [(i,j,k) for i in range(10) for j in range(10) for k in range(10)]: pass
Vous noterez la légèreté de l'ensemble, surtout quand on augmente en dimension.
C'est pourquoi la fonction suivante simplifie la lisibilité et marche avec un nombre indéterminée de liste :
def prod(*args): if len(args) == 1: return [(x,) for x in args[0]] return [(i,) + j for j in prod(*args[1:]) for i in args[0]] for x,y,z in prod(range(10),range(10),range(10)): pass
La fonction est particulièrement simple et totalement illisible car il s'est agit pour moi de faire un défi une ligne, mais vous pouvez la dérouler pour obtenir quelque chose de plus lisible.
Combinaisons
Soit une liste d'éléments. Comment obtenir toutes les combinaisons possibles avec ces éléments ? La solution est rudement intéressant d'un point de vu logique :
items = ('a','b','c')
sol = []
for i in range(2 ** len(items)):
sol.append([item for j,item in enumerate(items) if (i >> j) &1])
print sol
L'explication est plus tordue par contre :(
Tout d'abord, combien de combinaisons sont possibles ? 2 ** len(items). Nous allons donc attribuer à chacune de ces combinaisons un nombre. Dans l'exemple ici celui-ci va de 0 à 7.
L'astuce ici consiste à compter en binaire jusqu'a 7 et à considérer en gardant l'ordre de la liste, que si l'on rencontre un bit vrai, la valeur sera dans la liste, sinon non :
0 000 _ 1 001 c 2 010 _b_ 3 011 _bc 4 100 a__ 5 101 a_c 6 110 ab_ 7 111 abc
Pour cela l'on va utiliser la liste [item for j,item in enumerate(items)] qui dans le cas présent énumère tous les éléments de la liste en mettant dans la valeur de j la position de chaque élément. Le teste conditionnel suivant est composé de deux opérateurs binaires. Le premier, >> consiste en un décalage. C'est à dire que l'on prend le nombre binaire et qu'on le tronque de certains bits à la fin. Ainsi en décalant à chaque fois d'un cran, on pourra obtenir tous les bits qui forment notre nombre en bit de poids faible (le plus petit).
Il suffit alors d'utiliser l'opérateur & logique qui renvoie un nombre binaire avec des 1 là où tous les bits des deux nombres sont à 1 et des 0 sinon. Comme le nombre de droite est 1, il n'a qu'un seul bit positif, le bit de poids faible. Ainsi nous renvoyons un binaire qui a tous ses bits à zéros, sauf le bit de poids faible qui dépend de la valeur du bit de poids faible de notre autre nombre.
Désolé pour la présentation médiocre, je suis en plein changements dans le blog et voila... Vivement LaTeX dans l'html.
Commentaires
Jeudi 21 Juillet 2005 22:05:29 - S.F. Lien
Y'avait pas une fonction native pour les conversions de base ?
Vendredi 22 Juillet 2005 22:25:54 - Guillaume
Je ne l'ai pas trouvé...
Réagissez
En fait non ! Trop de smap