On précise dans cette page quelques notations et propriétés sur les logarithmes nécessaires pour un exposé clair sur quelques questions de complexité.

Un élève de terminale scientifique manipule en général le logarithme à base 10 en sciences-physiques, le logarithme à base e (logarithme népérien) en mathématiques et le logarithme à base 2 en ISN.

Ces fonctions ne sont distinctes qu'à un coefficient multiplicateur près : \[\forall x\in\left]0~;~+\infty\right[ \ \ \log_{10}(x) = \frac{\ln(x)}{\ln(10)}\] \[\forall x\in\left]0~;~+\infty\right[ \ \ \log_{2}(x) = \frac{\ln(x)}{\ln(2)}\]

Relation fonctionnelle.

\[\forall a\in \left]0~;~+\infty\right[, \forall b \in\left]0~;~+\infty\right[ \ \ \ln(a\times b)=\ln(a)+\ln(b) \] Et bien sûr (puisqu'il suffit de multiplier ln par un nombre constant pour obtenir log₁₀, idem pour log₂) : \[\forall a\in \left]0~;~+\infty\right[, \forall b \in\left]0~;~+\infty\right[ \ \ \log_{10}(a\times b)=\log_{10}(a)+\log_{10}(b) \] \[\forall a\in \left]0~;~+\infty\right[, \forall b \in\left]0~;~+\infty\right[ \ \ \log_{2}(a\times b)=\log_{2}(a)+\log_{2}(b) \]

Une conséquence

\[\forall a\in \left]0~;~+\infty\right[, \forall n \in\mathbb{N} \ \ \ln(a^n)=n\ln(a) \] \[\forall a\in \left]0~;~+\infty\right[, \forall n \in\mathbb{N} \ \ \log_{10}(a^n)=n\log_{10}(a) \] \[\forall a\in \left]0~;~+\infty\right[, \forall n \in\mathbb{N} \ \ \log_{2}(a^n)=n\log_{2}(a) \]

Croissance.

Seconde propriété : les fonctions log (pour les bases $p>1$ ) sont définies sur ]0 ; +∞ [ et strictement croissantes sur ]0 ; +∞ [.

Fonction réciproque.

Soit a un réel strictement positif. La fonction log_a est la fonction réciproque de la fonction x ↦ a^x.

\[\forall x\in\mathbb{R}, \ \forall y\in\left]0~;~+\infty\right[\ \colon \ \ 2^x=y \Longleftrightarrow x=\log_{2}(y) \] \[\forall x\in\mathbb{R}, \ \forall y\in\left]0~;~+\infty\right[\ \colon \ \ 10^x=y \Longleftrightarrow x=\log_{10}(y) \] \[\forall x\in\mathbb{R}, \ \forall y\in\left]0~;~+\infty\right[\ \colon \ \ e^x=y \Longleftrightarrow x=\ln(y) \]

En particulier : \[ \forall x\in\mathbb{R} \ \ \log_{10}(10^x) =x \] \[ \forall y\in\left]0~;~+\infty\right[\ \ \ 10^{\log_{10}(y)}=y \] \[ \forall x\in\mathbb{R} \ \ \log_{2}(2^x) =x \] \[ \forall y\in\left]0~;~+\infty\right[\ \ \ 2^{\log_{2}(y)}=y \] \[ \forall x\in\mathbb{R} \ \ \ln(e^x) =x \] \[ \forall y\in\left]0~;~+\infty\right[\ \ \ e^{\ln(y)}=y \]

En python, log désigne la fonction ln. Il faut préciser la base dans les autres cas.

from math import log

ln = log  

def log_10(x) :
	return log(x, 10)
 
def log_2(x) :
	return log(x, 2)


for x in (1, 10, 100, 1000, 10000, 100000, 1000000) :
	print('Image de {} par la fonction ln : {}.'.format(x,ln(x)) )

print()

for x in (1, 10, 100, 1000, 10000, 100000, 1000000) :
	print('Image de {} par la fonction log décimal : {}.'.format(x,log_10(x)) )


print()

for x in (1, 2, 8, 16, 100, 1000, 10000, 100000, 1000000) :
	print('Image de {} par la fonction log binaire : {}.'.format(x,log_2(x)) )

Définition

Soit x un nombre réel strictement positif.
Nous appellerons logarithme entier binaire de x et noterons par \[ \text{blog}(x) = \lceil \log_2(x) \rceil \] la partie entière supérieure de log₂(x).

En particulier : \[ \text{blog}(2^p) = \lceil \log_2(2^p) \rceil \] soit \[ \text{blog}(2^p) = p \]

Définition équivalente

Soit x un réel strictement positif. x est nécessairement compris entre deux puissances successives de 2. Plus précisément, il existe un entier n tel que \[ 2^{n-1} < x \leqslant 2^n \] On a alors blog(x)=n.
blog(x) est donc le plus petit entier n tel que \( x \leqslant 2^n \).

Justification.

De \[ 2^{n-1} < x \leqslant 2^n \] on déduit (la fonction log étant strictement croissante sur ]0 ; +∞ [ ) \[ \log_2( 2^{n-1} ) < \log_2(x) \leqslant \log_2(2^n) \] ce qui s'écrit aussi : \[ n-1 < \log_2(x) \leqslant n \] ou encore \[ n = \lceil \log_2(x) \rceil\]

Exemples

• \( 8 = 2^3 \), on a \( \text{blog}(8) = \lceil \log_2(2^3) \rceil = \lceil 3 \rceil = 3\) . Ce que l'on retrouve avec ce qui précède et l'encadrement \( 2^2 < 8 \leqslant 2^3 \).
• \( 2^3 < 9 \leqslant 2^4 \) donc \( \text{blog}(9) = 4 \).
• \( 2^{-1} < 0{,}7 \leqslant 2^0 \) donc \( \text{blog}(0{,}7) = 0 \).

Code python

D'après ce qui précède, pour tout réel \( x > 0 \) , si \( n = \text{blog}(x) \), on a : \[ 1 < \frac{x}{2^{n-1}} \text{ et } \frac{x}{2^{n }} \leqslant 1 \] \( \text{blog}(x) \) est le plus petit entier n tel que \[\frac{x}{2^n} \leqslant 1\]

Pour \( x \geqslant 1 \), \( \text{blog}(x) \) est donc le nombre minimum de divisions par 2 qu'il faut appliquer à \(x\) pour obtenir un nombre valant au plus 1.

D'où un programme simple de calcul de \( \text{blog}(x) \) pour \( x \geqslant 1 \) .

from math import log, ceil

 
def blog(x) :
	""" 
		x est un réel supérieur ou égal à 1.
		blog(x) est la partie entière supérieure de log à base 2 de x.
	"""
	n = 0
	while x>1 :
		x/=2
		n+=1
	return n
	
def logEntier(x) :
	""" 
		x est un réel supérieur à 0.
		logEntier(x) est la partie entière supérieure de log à base 2 de x.
	"""
	return ceil(log(x,2))


for x in (1, 1.6, 2,3, 4, 7, 8, 14, 15, 16, 17) : 
	print('blog   de {} : {}.'.format(x, blog(x)) )
	print('Avec la fonction log du module math : {} '.format(logEntier(x) ) )
	print()

Si on veut étendre cette approche aux réels de l'intervalle \( \left] 0 ; 1 \right[ \) :

	from math import log, ceil

def blog(x) :
	""" 
		x est un réel supérieur à 0.
		blog(x) est la partie entière supérieure de log à base 2 de x.
	"""
	n = 0
	if( x >= 1) :
		while x > 1 :
			x /= 2
			n += 1
		return n
	else :
		while x <= 1 :
			x *= 2
			n -= 1
		return n+1
	
def logEntier(x) :
	""" 
		x est un réel supérieur à 0.
		logEntier(x) est la partie entière supérieure de log à base 2 de x.
	"""
	return ceil(log(x,2))


for x in (0.1, 0.25, 0.4, 0.5, 0.7, 0.9, 1, 1.6, 2,3, 4, 7, 8, 14, 15, 16, 17) : 
	print(logEntier(x) == blog(x), end = ' ')

Propriété

Soit n un entier (différent de 0).
Le nombre de chiffres de l'écriture décimale de n est \[ \lfloor \log_{10}(n) \rfloor +1 \] (où ⌊. ⌋ désigne la fonction partie entière).

Le nombre de chiffres de l'écriture binaire de n est \[ \lfloor \log_{2}(n) \rfloor +1 \]

Démonstration

La démonstration est exposée dans le cas de la base 10. Elle est analogue en base 2.

Un entier à 3 chiffres est un entier n vérifiant 10² ≤ n < 10³.
De façon plus générale, un entier à p chiffres vérifie 10^p-1 ≤ n < 10^p.

Comme la fonction log₁₀ est strictement croissante sur ]0 ; +∞ [, on a pour un tel entier : \[ \log_{10}(10^{p-1}) \leqslant \log_{10}(n) < \log_{10}(10^p) \] Et la fonction log₁₀ étant la fonction réciproque de la fonction x ↦ 10^x, ceci s'écrit : \[ p-1 \leqslant \log_{10}(n) < p \]

On a donc : \( p-1 = \lfloor \log_{10}(n) \rfloor \) , ce qui est le résultat annoncé.