Logaritme binari

En matemàtiques, el logaritme binari (log₂ n) és el logaritme en base 2. És la funció inversa de n ↦ 2ⁿ. El logaritme binari de n és la potència a la qual cal elevar el nombre 2 per obtenir el valor n. Això fa útil el logaritme binari per a tot el que impliqui potències de 2. Per exemple, el logaritme binari d'1 és 0, el logaritme binari de 2 és 1, el logaritme binari de 4 és 2, el logaritme binari de 8 és 3, el logaritme binari de 16 és 4 i el logaritme binari de 32 és 5.

Aplicacions

Teoria de la Informació

El logaritme binari s'utilitza sovint en informàtica i teoria de la informació perquè està molt relacionat amb el sistema de numeració binari. Segons l'especificació ISO s'escriu lb (n). El nombre de dígits (bits) en la representació binària d'un enter positiu n és la part entera de 1 + lb n, és a dir:

\lfloor \operatorname {lb} \,n\rfloor +1.\,

En teoria de la informació, la definició de la quantitat d'informació i entropia d'informació fa servir el logaritme binari; això és necessari perquè la unitat d'informació, el bit, es refereix a informació que resulta el coneixement d'un fet que pot tenir dues alternatives igualment probables.

Complexitat computacional

El logaritme binari també apareix sovint en l'anàlisi d'algorismes. Si un nombre n més gran que 1 es divideix entre 2 repetidament, el nombre d'iteracions necessitades per aconseguir un valor com a màxim 1 és una altra vegada la part entera de lb n. Aquesta idea s'utilitza en l'anàlisi de diveres estructuresde dades i d'algorismes. Per exemple, en la cerca binària, la mida del problema a resoldre es redueix a la meitat a cada iteració, i per això calen aproximadament n iteracions per obtenir un problema de mida 1, que es resol fàcilment en temps constant. De manera similar, un arbre de recerca binari perfectament equilibrat que conté n elements té alçada lb n + 1.

Tanmateix, el temps d'execució d'un algorisme s'expressa normalment en notació d'O gran, ignorant factors constants. Com que log₂ n = (1/log_k 2)log_k n, on k pot ser qualsevol nombre més gran que 1, els algorismes que s'executen en temps O (log₂ n) també es pot dir que s'executen, per exemple en temps O (log₁₃ n). Per això la base del logaritme en expressions com O (log n) o O (n log n) no és important.

En altres contexts, tanmateix, cal especificar la base del logaritme. Per exemple O(2^{lb n}) no és igual que O(2^{ln n}) perquè el primer és igual a O(n) i el segon a O(n^0.6931....

Els algorismes amb temps d'execució n lb n de vegades s'anomenen linearithmics. Alguns exemples d'algorismes amb temps d'execució O (lb n) o O (n lb n) són:

Fent servir calculadores

Una manera fàcil de calcular el log₂(n) en calculadores que no tenen la funció log₂ és fer servir el logaritme natural "ln" o el logaritme decimal "log", que es troben en la majoria de "les calculadores científiques". La fórmula de canvi de base de logaritme és:

log₂(n) = ln(n)/ln(2) = log(n)/log(2)

així

log₂(n) = log_e(n)×1.442695... = log₁₀(n)×3.321928...

Algorisme

Enter

Per a dominis i recorreguts enters, el logaritme binari es pot calcular arrodonint amunt o avall. Aquestes dues formes de logaritme binari enter es relacionen per aquesta fórmula:

\lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{ if }}n\geq 1.

^[1]

La definició es pot estendre definint $\lfloor \log _{2}(0)\rfloor =-1$ . Aquesta funció està relacionada amb el nombre de zeros de la representació binària amb 32 bits sense signe de x, nlz(x).

\lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (x).

^[1]

El codi exemple següent, una mica canviat, en llenguatge C calcula el logaritme binari (arrodonint cap avall) d'un enter.^[1] L'operador '>>' representa 'decalatge a la dreta' sense signe. L'arrodoniment cap avall del logaritme binari és idèntic a calcular la posició del bit més significatiu.

/**
* Retorna el logaritme binari enter arrodonit cap avall per a un enter de 32 bits.
* es retorna −1 si ''n'' és 0.
* /
int floorLog2(unsigned int n) {
 if (n == 0)
 return -1;

 int pos = 0;
 if (n >= 1<<16) { n >>= 16; pos += 16; }
 if (n >= 1<< 8) { n >>= 8; pos += 8; }
 if (n >= 1<< 4) { n >>= 4; pos += 4; }
 if (n >= 1<< 2) { n >>= 2; pos += 2; }
 if (n >= 1<< 1) { pos += 1; }
 return pos;
}

Nombre real

Per a un nombre real positiu general, el logaritme binari es pot calcular en dues parts:

Calcular la part entera, $\lfloor \operatorname {lb} (x)\rfloor$
Calcular la part fraccionària

Calcular la part entera és directe. Per a qualsevol x > 0, existeix un enter únic n tal que 2ⁿ ≤ x < 2^{n +1}, o equivalentment 1 ≤ 2⁻ⁿx < 2. Ara la part entera del logaritme és simplement n, i la part fraccionària és lb(2⁻ⁿx). En altres paraules:

\operatorname {lb} (x)=n+\operatorname {lb} (y)\quad {\text{on }}y=2^{-n}x{\text{ i }}y\in [1,2)

La part fraccionària del resultat és $\operatorname {lb} y$ , i es pot calcular recursivament, fent servir només operacions elementals de multiplicació i divisió. Per calcular la part fraccionària:

Es comença amb un nombre real $y\in [1,2)$ . Si $y=1$ , llavors s'ha acabat i la part fraccionària és zero.
Altrament, $y$ s'eleva al quadrat repetidament fins que el resultat és $z\in [2,4)$ . Sia $m$ el nombre de vegades que ha calgut elevar al quadrat. És a dir, $z=y^{2\uparrow m}$ amb $m$ escollit tal que $z\in [2,4)$ .
Calculant el logaritme als dos costats i fent una mica d'àlgebra:
${\begin{aligned}\operatorname {lb} \,z&=2^{m}\operatorname {lb} \,y\\\operatorname {lb} \,y&={\frac {\operatorname {lb} z}{2^{m}}}\\&={\frac {1+\operatorname {lb} (z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\operatorname {lb} (z/2)\end{aligned}}$
Observeu que $z/2$ és altra vegada un nombre real en l'interval $[1,2)$ .
Tornar al pas 1, i calcular el logaritme binari de $z/2$ fent servir el mateix mètode recursivament.

El resultat d'això s'expressa per les fórmules següents, en les quals $m_{i}$ el nombre de vegades que cal elevar al quadrat en la i-èsima recursió de l'algorisme:

{\begin{aligned}\operatorname {lb} \,x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{-m_{3}}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2}}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{aligned}}

En el cas especial on la part fraccionària al pas 1 resulta ser zero, això és una successió finita que acaba a algun punt. Altrament, és una sèrie infinita que convergeix segons el criteri de d'Alembert, ja que cada terme és estrictament menor que el previ (ja que tots els $m_{i}>0$ ). A la pràctica, aquesta sèrie infinita s'ha de truncar per arribar a un resultat aproximat. Si la sèrie es trunca després del i-èsim terme, llavors l'error en el resultat és menor que $2^{-(m_{1}+m_{2}+\cdots +m_{i})}$ .

Codi d'exemple

El programa en Python següent calcula el logaritme binari fent servir el mètode recursiu que s'ha explicat a dalt, mostrant els passos pel camí:^[2]

def lg(x):
 ip = 0
 rem = x

 # Part entera
 while rem<1:
 ip -= 1
 rem *= 2
 while rem>=2:
 ip += 1
 rem /= 2
 print "lg(%g) = %d + lg(%g)" % (x, ip, rem)

 # Part Fraccionària
 res = ip + frac_lg(rem)

 return res

 
def frac_lg(x, fp=1.0, tol=1e-10):
 assert 1<=x<2

 # Acabar la recussió si s'està prou a prop
 if fp<tol:
 return 0



 # square until >= 2
 rem = x
 m = 0
 while rem < 2:
 m += 1
 fp /= 2
 rem *= rem

 # ara:
 # rem = x**2**m, fp = 2**-m
 # => lg(rem) = lg(x)*2**m = lg(x)/fp
 # => lg(x) = fp * (lg(rem/2) + 1)
 # = fp + fp*lg(rem/2)
 # hora de fer recussió!

 print "lg(x=%g) \t= 2**%d * (1 + lg(%g))" % (x, -m, rem/2)
 return fp + frac_lg(rem/2, fp)

 
if __name__ == '__main__':
 value = 4.5
 print " X =", value
 result = lg(value)
 print "lg(X) =", result

# Exemple de resultat
#
# $ python log2.py 
# X = 4.5
# lg(4.5) = 2 + lg(1.125)
# lg(x=1.125) 	= 2**-3 * (1 + lg(1.28289))
# lg(x=1.28289) 	= 2**-2 * (1 + lg(1.35435))
# lg(x=1.35435) 	= 2**-2 * (1 + lg(1.68226))
# lg(x=1.68226) 	= 2**-1 * (1 + lg(1.415))
# lg(x=1.415) 	= 2**-1 * (1 + lg(1.00111))
# lg(x=1.00111) 	= 2**-10 * (1 + lg(1.55742))
# lg(x=1.55742) 	= 2**-1 * (1 + lg(1.21278))
# lg(x=1.21278) 	= 2**-2 * (1 + lg(1.08166))
# lg(x=1.08166) 	= 2**-4 * (1 + lg(1.75563))
# lg(x=1.75563) 	= 2**-1 * (1 + lg(1.54113))
# lg(x=1.54113) 	= 2**-1 * (1 + lg(1.18753))
# lg(x=1.18753) 	= 2**-3 * (1 + lg(1.97759))
# lg(x=1.97759) 	= 2**-1 * (1 + lg(1.95543))
# lg(x=1.95543) 	= 2**-1 * (1 + lg(1.91185))
# lg(x=1.91185) 	= 2**-1 * (1 + lg(1.82758))
# lg(X) = 2.16992500139
#

Donat que Python no optimitza la recurrència de cua, això es pot implementar més eficaçment amb iteració. Aquí hi ha una versió iterativa del mateix algorisme en Perl:

sub lg {
 my $x = shift;
 my $tol = shift || 1e-13;
 my $res = 0.0;

 while ($x < 1) {
	$res -= 1;
	$x *= 2;
 }
 while ($x >= 2) {
	$res += 1;
	$x /= 2;
 }
 my $fp = 1.0;
 while ($fp >= $tol) {
	$fp /= 2;
	$x *= $x;
	if ($x >= 2) {
		$x /= 2;
		$res += $fp;
	}
 }
 $res 
}

printf "x = %g\nlg(x) = %g\n", 4.5, lg(4.5);

Referències

↑ ^1,0 ^1,1 ^1,2 Warren Jr., Henry S. Hacker's Delight. Addison Wesley, 2002, pp. 215. ISBN 978-0201914658.
↑ adaptat de [% de http://en.literateprograms.org/Logarithm_Function_%28Python Arxivat 2016-03-03 a Wayback Machine. 29 Funció de Logaritme (Pitó)]

Vegeu també

Logaritme natural (base e)
Logaritme

[Hackers-1] 1,0 ^1,1 ^1,2 Warren Jr., Henry S. Hacker's Delight. Addison Wesley, 2002, pp. 215. ISBN 978-0201914658.

[2] tat de [% de http://en.literateprograms.org/Logarithm_Function_%28Python Arxivat 2016-03-03 a Wayback Machine. 29 Funció de Logaritme (Pitó)]

[1]

[2]