Codificación de Fibonacci

La codificación de Fibonacci, es un método para codificar números enteros positivos utilizando como base la sucesión de Fibonacci.

Este documento seguirá la siguiente estructura: En la primera sección, definiremos algunos resultados previos, como la sucesión de Fibonacci y el teorema en el que se basa la codificación. En la segunda sección, exploraremos el proceso de codificación en si, acompañado de algunos fragmentos de código que ilustrarán cómo llevar a cabo esta codificación. En la última sección, explicaremos cómo realizar la decodificación de un número.

Resultados previos

En esta sección, definiremos la sucesión de Fibonacci, una ecuación que nos permite calcular el n-ésimo término de la sucesión de Fibonacci, y, por último, examinaremos el teorema de Zeckendorf, el cual proporciona la base para la codificación de Fibonacci.

Sucesión de Fibonacci

La sucesión de Fibonacci es una secuencia de números naturales definidos por la siguiente relación de recurrencia:

\[F_n=F_{n-1}+F_{n-2}\]

Se establecen los dos primeros elementos de la sucesión como \(F_0:=0\) y \(F_1:=1\).

Los primeros elementos de la sucesión de Fibonacci son:

\(F_0\)	\(F_1\)	\(F_2\)	\(F_3\)	\(F_4\)	\(F_5\)	\(F_6\)	\(F_7\)	\(F_8\)	\(F_9\)	\(F_{10}\)	\(F_{11}\)
0	1	1	2	3	5	8	13	21	34	55	89

Inicialmente, Fibonacci definió su sucesión con los valores \(F_1=1\) y \(F_2=1\) debido a su interés en resolver un problema de cría de conejos, donde \(F_1\) y \(F_2\) representan los dos primeros conejos de la población. Esta sucesión presenta numerosas conexiones con otros números y objetos matemáticos, como el número áureo. Puede encontrar más información sobre esta sucesión en la página de Wikipedia.

Una Forma Rápida de Calcular el N-ésimo Término de Fibonacci

En esta sección, presentaremos una forma de calcular el n-ésimo término de la sucesión de Fibonacci sin necesidad de conocer los dos últimos términos de la sucesión.

Para mostrar esta ecuación, primero utilizaremos la relación de recurrencia que cumple la sucesión de Fibonacci:

\[ F_{n+1} = F_{n} + F_{n-1} \]

Además, usaremos que \(F_n=F_n\). Estas dos ecuaciones las podemos escribir como un sistema matriz por vector:

\[ \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} \]

Definamos \(M\) como la matriz \(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\) y \(V_n\) como el vector columna \(\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}\).

Entonces, la relación de recurrencia puede expresarse como\(V_{n+1} = M V_{n}\). De aquí se desprende que:

\[ V_{n+1}=M V_{n}=M M V_{n-1}=M ^2 V_{n-1}=M ^3 V_{n-2}=\cdots =M ^n V_1 \]

Para calcular \(M ^ n\), vamos a diagonalizar a \(M\) como \(M = P D P^{-1}\), donde \(D\) es una matriz diagonal que contiene los eigenvalores de \(M\), y \(P\) es la matriz que contiene sus eigenvectores.

Los eigenvalores de \(M\) son: \(\varphi= \frac{1 + \sqrt{5}}{2}\) (número áureo) y \(\overline{\varphi} = \frac{1 - \sqrt{5}}{2}\). La matriz diagonal \(D\) es :

\[ D = \begin{bmatrix} \overline{\varphi} & 0 \\ 0 & \varphi \end{bmatrix} \]

Luego, al calcular los vectores propios de \(M\), obtenemos que la matriz \(P\) es:

\[ P = \begin{bmatrix} \overline{\varphi} & \varphi \\ 1 & 1 \end{bmatrix} \]

La inversa de \(P\) es:

\[ P ^{-1} = \begin{bmatrix} \frac{-\sqrt{5}}{5}& \frac{5+\sqrt{5}}{10} \\ \frac{\sqrt{5}}{5} & \frac{5+\sqrt{5}}{10} \end{bmatrix} \]

Finalmente, obtenemos que:

\[\begin{align*} V_{n+1}&=M^n V_0\\ &=P D^n P^{-1}V_1\\ &= \begin{bmatrix} \overline{\varphi} & \varphi \\ 1 & 1 \end{bmatrix} \begin{bmatrix} \overline{\varphi} ^n & 0 \\ 0 & \varphi ^n \end{bmatrix} \begin{bmatrix} \frac{-\sqrt{5}}{5}& \frac{5+\sqrt{5}}{10} \\ \frac{\sqrt{5}}{5} & \frac{5+\sqrt{5}}{10} \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \end{align*} \]

Realizando la multiplicación de la segunda fila de la matriz, obtenemos la siguiente ecuación:

\[F_n=\frac{\sqrt{5}}{5}( \varphi^n- \overline{\varphi}^n )\quad \forall n\in\mathbb{N} \]

Esta ecuación se conoce como Fórmula de Binet.

Con esta ecuación, calcular el n-ésimo término de la sucesión de Fibonacci toma tiempo \(\Theta(\log n)\), mientras que con la ecuación de recurrencia nos tomaría tiempo \(O(n)\).

Teorema de Zeckendorf

El Teorema de Zeckendorf es la base de la codificación de Fibonacci. Puede enunciarse de la siguiente manera:

Teorema de Zeckendorf (1972): Para todo número entero \(N>0\), existe un \(k\in\mathbb{N}\) y existen unos únicos \(d_i\in\{0,1\}\) con \(i=0,\ldots,k-1\), tales que

\[N=\sum_{i=0}^{k-1}d_iF_{i+2} \]

Este resultado nos asegura que todo número natural puede descomponerse como la suma finita de algunos de los elementos de la sucesión de Fibonacci.

A continuación, daremos algunos ejemplos de esta descomposición.

Numero	Suma de la sucesión de Fibonacci
\(1\)	\(F_2\)
\(2\)	\(F_3\)
\(3\)	\(F_4\)
\(4\)	\(F_2+F_4\)
\(5\)	\(F_5\)
\(6\)	\(F_2+F_5\)
\(7\)	\(F_3+F_5\)
\(8\)	\(F_6\)
\(9\)	\(F_2+F_6\)
\(10\)	\(F_3+F_6\)
\(11\)	\(F_4+F_6\)

Codificación de Fibonacci

La codificación de Fibonacci se basa en el Teorema de Zeckendorf, y esta codificación se expresa como \(d_0d_1\cdots d_{k-1}1\), donde los \(d_i\) son determinados por el Teorema de Zeckendorf.

Como consecuencia del Teorema de Zeckendorf, para cualquier número natural distinto de cero, siempre existe una única codificación en bits de la forma \(d_0d_1\cdots d_{k-1}1\). Entonces, ¿cómo encontramos los \(d_i\) de esta codificación? Para hacerlo, podemos seguir el siguiente procedimiento:

Encuentra el número de Fibonacci más grande igual o menor que \(N\), llamémoslo \(F_{k+2}\).
Genera una cadena de bits \(B=1\).
Llamemos \(r=N-F_{k+2}\).
Si \(r\geq 0\), actualizamos \(N=r\), \(k=k-1\), y agregamos un 1 a la izquierda de \(B\).
En caso contrario, actualizamos \(k=k-1\) y agregamos un 0 a la izquierda de \(B\).
Repite los pasos 3, 4 y 5 hasta que \(k<0\).
Se finaliza, retornando \(B\).

Para mayor claridad, codificaremos el número 9 a modo de ejemplo.

Ejemplo: Calculando los primeros 7 términos de la sucesión de Fibonacci, notamos que \(F_6=8\) y \(F_7=13\), por lo tanto, \(F_6=8\) es el término más grande igual o menor a 9. Aquí, \(k=4\).

Generamos a \(B=1\), y \(r=9-F_6=1\).

Aplicamos el paso 4, luego \(B=11\), \(N=1\) y \(k=4-1=3\).
Aplicamos el paso 3, \(r=1-F_{k+2}=1-F_{3+2}=1-5=-4\).
Aplicamos el paso 5, luego \(B=011\) y \(k=3-1=2\).
Aplicamos el paso 3, \(r=1-F_{k+2}=1-F_{2+2}=1-3=-2\).
Aplicamos el paso 5, luego \(B=0011\) y \(k=2-1=1\).
Aplicamos el paso 3, \(r=1-F_{k+2}=1-F_{1+2}=1-2=-1\).
Aplicamos el paso 5, luego \(B=00011\) y \(k=1-1=0\).
Aplicamos el paso 3, \(r=1-F_{k+2}=1-F_{0+2}=1-1=0\).
Aplicamos el paso 4, luego \(B=100011\), \(N=0\) y \(k=0-1=-1\).

Con esto, completamos el paso 6. La codificación de Fibonacci de 9 es \(B=100011\).

Implementación en C++

A continuación, proporcionaremos una implementación de la codificación de Fibonacci en C++.

Lo primero que debemos implementar es la búsqueda del número de Fibonacci más grande

Como se puede dar cuenta, la implementación anterior guarda todos los números de Fibonacci que sea menor o igual a \(N\). Para ello, podemos basarnos en la búsqueda lineal junto con la fórmula de recurrencia para encontrar este número. href="#__codelineno-0-1">vector<unsigned int> FibonacciLinear(unsigned int N) span> vector<unsigned int> F; if (N == 0) cerr << "Solo se puede codificar numeros mayores a cero" << endl; else if (N == 1) F.push_back(1); else if (N == 2) { F.push_back(1); F.push_back(2); } else { F.push_back(1); F.push_back(2); unsigned int f = 3; while (N > f) { F.push_back(f); int r = F.size(); f = F[r - 2] + F[r - 1]; } } return F; } hasta encontrar el número buscado. Vamos a usar el vector \(F\) para ahorrarnos algunos cálculos en el siguiente paso. Ahora implementaremos el resto de pasos y guardaremos la codificación en un string.

string  FibonacciCoding(unsigned  int  N)
{
    vector<unsigned  int>  F  =  FibonacciLinear(N);
    string  B  =  "1";
    int  p  =  F.size();
    if  (p  ==  1)
        B  =  "1"  +  B;
    else
    {
        unsigned  int  Naux  =  N;
        for  (int  i  =  p  -  1;  i  >=  0;  i--)
        {
            int  r  =  Naux  -  F[i];
            if  (r  >=  0)
            {
                Naux  =  r;
                B  =  "1"  +  B;
            }
            else
                B  =  "0"  +  B;
        }
    }
    return  B;
}

Sea \(K\) el número más grande tal que \(N\geq F_{K+2}\). La implementación anterior toma un tiempo \(O(K)\) en el peor caso, usando un espacio \(O(K)\).

Existe otra implementación de la codificación de Fibonacci que utiliza un espacio \(O(1)\), pero usa un tiempo \(O(K\log K)\) en el peor caso. Esta implementación, para ahorrarse el espacio ocupado en el cálculo de la sucesión de Fibonacci, utiliza la fórmula de Binet para calcular estos números.

A continuación, mostraremos una implementación de la fórmula de Binet.

unsigned  int  BinetFormula(int  i)
{
    double  F  =  (sqrt(5)  /  5)  *  (pow((1  +  sqrt(5))  /  2,  i)  +  pow((1  -  sqrt(5))  /  2,  i));
    return  static_cast<unsigned  int>(round(F));
}

Ahora debemos implementar una función que determine el valor del número \(k\) más grande tal que \(N\geq F_{k+2}\). Una forma de hacerlo es usar la misma idea de la implementación anterior, utilizar búsqueda lineal para encontrar el \(k\). Para ahorrarse espacio, en ese caso siempre se deben tener guardados los dos últimos términos de la sucesión. Otra forma de obtener lo mismo es, en vez de usar búsqueda lineal, usar búsqueda doblada.

unsigned  int  FibonacciDubbed(unsigned  int  N)
{
    if  (N  ==  0)
        cerr  <<  "Solo se puede codificar numeros mayores a cero"  <<  endl;
    else  if  (N  ==  1)
        return  2;
    else  if  (N  ==  2)
        return  3;
    else
    {
        int  i  =  1;
        while  (BinetFormula(i)  <  N)
            i  =  i  *  2;
        int  left  =  i  /  2,  right  =  i;
        while  (left  <=  right)
        {
            int  m  =  left  +  (right  -  left)  /  2;
            if  (BinetFormula(m)  <=  N  &&  BinetFormula(m  +  1)  >  N)
                return  m;
            if  (BinetFormula(m)  <  N)
                left  =  m  +  1;
            else
                right  =  m  -  1;
        }
    }
}

Ahora sólo nos queda implementar los pasos del 2 al 7, para ello realizaremos algunas modificaciones al código anterior.

string  FibonacciCoding(unsigned  int  N)
{
    unsigned  int  K  =  FibonacciDubbed(N);
    string  B  =  "1";
    if  (K  ==  2)
        B  =  "1"  +  B;
    else
    {
        unsigned  int  K  =  K  -  2,  Naux  =  N;
        for  (int  i  =  K;  i  >=  0;  i--)
        {
            int  r  =  Naux  -  BinetFormula(i  +  2);
            if  (r  >=  0)
            {
                Naux  =  r;
                B  =  "1"  +  B;
            }
            else
                B  =  "0"  +  B;
        }
    }
    return  B;
}

Decodificación

Para decodificar una cadena de bits \(B\), se puede seguir el siguiente procedimiento:

A la cadena de bits \(B\) le quitamos el último bit, y sea \(N=0\).
Para todo \(i=0,\ldots,t=\) largo de \(B-1\). Si \(B(i)=1\), calcular \(N=N+F_{i+2}\).
Retornar \(N\).

Recordemos que el número 9 se codifica como \(B=100011\), veamos si al aplicar estas reglas de decodificación podemos recuperar el número 9.

Ejemplo: Tomemos la cadena de bits \(B=100011\). Comenzamos quitando el último bit, obteniendo que \(B=10001\).

Sea \(N=0\). Recorremos \(B\) de izquierda a derecha.

Para \(i=0\). Como \(B(i)=1\), calculamos \(N=N+F_{i+2}=0+1=1\).
Para \(i=1\). Como \(B(i)=0\), no hacemos nada.
Para \(i=2\). Como \(B(i)=0\), no hacemos nada.
Para \(i=3\). Como \(B(i)=0\), no hacemos nada.
Para \(i=4\). Como \(B(i)=1\), calculamos \(N=N+F_{i+2}=1+8=9\).

El número codificado en \(B\) es 9.

Implementación en C++

Mostraremos una implementación de la decodificación en C++.

Como hicimos antes, daremos dos implementaciones. La primera hace uso de la fórmula de recurrencia de la sucesión.

unsigned  int  FibonacciDecoding(string  B)
{
    B.pop_back();
    if  (B.size()  ==  1)
        return  1;
    else
    {
        unsigned  int  F1  =  1,  F2  =  2,  N  =  0;
        if  (B[0]  ==  '1')
            N  +=  F1;
        if  (B[1]  ==  '1')
            N  +=  F2;
        if  (B.size()  ==  2)
            return  N;
        else
        {
            for  (int  i  =  2;  i  <  B.size();  i++)
            {
                unsigned  int  aux  =  F2;
                F2  =  F2  +  F1;
                F1  =  aux;
                if  (B[i]  ==  '1')
                    N  +=  F2;
            }
            return  N;
        }
    }
}

Esta implementación toma un tiempo \(O(|B|)\) en el peor caso y usa un espacio de \(O(1)\).

La segunda implementación de la decodificación hace uso de la fórmula de Binet.

unsigned  int  FibonacciDecoding(string  B)
{
    B.pop_back();
    unsigned  int  N  =  0;
    for  (int  i  =  0;  i  <  B.size();  i++)
    {
        if  (B[i]  ==  '1')
            N  +=  BinetFormula(i  +  2);
    }
    return  N;
}

Esta implementación toma un tiempo \(O(|B|\log|B|)\) en el peor caso y usa un espacio de \(O(1)\). En la práctica, la codificación de Fibonacci suele tener una gran cantidad de ceros, lo cual hace poco probable que se alcance la cota anterior.

Referencias

Hashemi, M., & Mehraban, E. (2021). Some New Codes on the \(k\)–Fibonacci Sequence. Mathematical Problems in Engineering, 2021, 1-13.
Beutelspacher, A., Petri, B., Beutelspacher, A., & Petri, B. (1996). Fibonacci-Zahlen. Der Goldene Schnitt, 87-98.
Zeckendorf, É. (1972). Representations des nombres naturels par une somme de nombres de fibonaccion de nombres de lucas. Bulletin de La Society Royale des Sciences de Liege, 179-182.