Logaritme binari

Gràfica del log₂n

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.

Contingut

1 Aplicacions
- 1.1 Teoria de la Informació
- 1.2 Complexitat computacional

2 Fent servir calculadores

3 Algorisme
- 3.1 Enter
- 3.2 Nombre real

4 Codi d'exemple

5 Referències

6 Vegeu també

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:

displaystyle lfloor operatorname lb ,nrfloor +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 forma 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:

quicksort de temps mitjà

arbres de cerca binaris

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:

displaystyle lfloor log _2(n)rfloor =lceil log _2(n+1)rceil -1,text if ngeq 1.

^[1]

La definició es pot estendre definint $displaystyle 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).

displaystyle 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, $displaystyle 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:

displaystyle operatorname lb (x)=n+operatorname lb (y)quad texton y=2^-nxtext i yin [1,2)

La part fraccionària del resultat és $displaystyle 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 $displaystyle yin [1,2)$ . Si $displaystyle 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 $displaystyle zin [2,4)$ . Sia $displaystyle m$ el nombre de vegades que ha calgut elevar al quadrat. És a dir, $displaystyle z=y^2uparrow m$ amb $displaystyle m$ escollit tal que $displaystyle zin [2,4)$ .

Calculant el logaritme als dos costats i fent una mica d'àlgebra:
$displaystyle beginalignedoperatorname lb ,z&=2^moperatorname lb ,y\operatorname lb ,y&=frac operatorname lb z2^m\&=frac 1+operatorname lb (z/2)2^m\&=2^-m+2^-moperatorname lb (z/2)endaligned$

Observeu que $displaystyle z/2$ és altra vegada un nombre real en l'interval $displaystyle [1,2)$ .

Tornar al pas 1, i calcular el logaritme binari de $displaystyle z/2$ fent servir el mateix mètode recursivament.

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

displaystyle beginalignedoperatorname lb ,x&=n+2^-m_1left(1+2^-m_2left(1+2^-m_3left(1+cdots right)right)right)\&=n+2^-m_1+2^-m_1-m_2+2^-m_1-m_2-m_3+cdots endaligned

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 $displaystyle 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 $displaystyle 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 

printf "x = %gnlg(x) = %gn", 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 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 29 Funció de Logaritme (Pitó)]

搜尋此網誌

Styjun