Logaritme binari

De Viquipèdia
Dreceres ràpides: navegació, cerca
Gràfica del log2 n

En matemàtiques, el logaritme binari (log2 n ) és el logaritme en base 2. És la funció inversa de n  ↦ 2n . El logaritme binari de n és la potència a la qual cal elevar el número 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 is 2, el logaritme binari de 8 és 3, el logaritme binari de 16 és 4 i el logaritme binari de 32 is 5.

Aplicacions[modifica | modifica el codi]

Teoria de la Informació[modifica | modifica el codi]

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 provables.

Complexitat computacional[modifica | modifica el codi]

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 log2 n = (1/logk  2)logk n, on k pot ser qualsevol nombre més gran que 1, els algorismes que s'executen en temps O (log2 n ) també es pot dir que s'executen, per exemple en temps O (log13 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(2lb n ) no és igual que O(2ln n) perquè el primer és igual a O(n) i el segon a O(n0.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[modifica | modifica el codi]

Una manera fàcil de calcular el log2(n) en calculadores que no tenen la funció log2 é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:

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

així

log2(n) = loge(n)×1.442695... = log10(n)×3.321928...

Algorisme[modifica | modifica el codi]

Enter[modifica | modifica el codi]

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 \ge 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[modifica | modifica el codi]

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

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

Calcular la part entera és directe. Per a qualsevol x > 0, existeix un enter únic n tal que 2n  ≤ x < 2n +1, o equivalentment 1 ≤ 2n x < 2. Ara la part emmntera del logaritme és simplement n, i la part fraccionària és lb(2nx). 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:

  1. 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.
  2. 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).
  3. Calculant el logaritme als dos costats i fent una mica d'àlgebra:
    \begin{align}
\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{align}
  4. Observeu que z/2 és altra vegada un nombre real en l'interval [1,2).
  5. 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-èssima recurssió de l'algorisme:

\begin{align}
\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{align}

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 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-èssim terme, llavors l'error en el resultat és menor que 2^{-(m_1+m_2+\cdots+m_i)}.


Codi d'exemple[modifica | modifica el codi]

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 aprop
    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[modifica | modifica el codi]

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

Vegeu també[modifica | modifica el codi]