Notebook 09
Série de Fibonacci, 1d array

Os dois primeiros números da sequência de Fibonacci são $x_0$ = 0 e $x_1$ =1. A partir deles os demais podem ser obtidos a partir de uma regra de recorrência:

A sequência de Fibonacci possui algumas propriedades peculiares. Considere o início da sequência:

Note que $x_3$ = 2 e que o número a cada 3 posições é múltiplo de $x_3$ (ou seja, múltiplo de 2): $x_6$ = 8, $x_9$ = 24, $x_{12}$ = 144 etc..

Algo semelhante acontece para que $x_4$ = 3: o número a cada 4 posições é múltiplo de $x_4$ (ou seja, múltiplo de 3): $x_8$ = 21, $x_12$ = 144 etc.

E assim sucessivamente: $x_5$ = 5 e o número a cada 5 posições é múltiplo de $x_5$ (ou seja, múltiplo de 5): $x_10$ = 55, $x_15$ = 610 etc.

O script deste documento gera uma matriz com os 78 primeiros números da sequência de Fibonacci (paramos no 78o. porque o maior inteiro "seguro" suportado pelo objeto Number do JavaScript é 2⁵³ − 1 = 9007199254740991 e o 80o. número de Fibonacci é maior do que isso; existem maneiras de lidar com números arbitrariamente grandes em JavaScript, mas no momento vamos nos ater ao básico).

Em seguida, percorre a lista de números gerados verificando se a regra acima realmente vale para todos os números a cada tês posições ($x_3$, $x_6$, $x_9$ etc.). Note o uso de %1 para verificar se a divisão do número por 1 deixa algum resto (esta é uma das maneiras possíveis de se obter a parte fracionária de um número, com um eventual caveat). Além disso o script imprime também uma matriz com os resultados da divisão, para facilitar a confirmação.

Exercícios

1. Verifique a validade da regra para os números nas posições $x_4$, $x_5$, $x_6$ e $x_7$.
Console: (20) [0, 1, 7, 48, ..., 1138818207635569] true (16) [0, 1, 11, 122, ..., 422297015595610] true (14) [0, 1, 18, 323, ..., 1118049290473933] true (12) [0, 1, 29, 842, ..., 425226130837289] true
2. Uma outra maneira de calcular a sequência de Fibonacci é através da equação:
\begin{equation} x_n = \frac{\varphi^n - (1-\varphi)^n}{\sqrt{5}} \end{equation}

Nessa equação, $\varphi$ é conhecida como a razão dourada (você não vai se arrepender se estudar um pouco mais sobre esse número!), que é dada por:

\begin{equation} \varphi = \frac{1+\sqrt{5}}{2} = 1,6180339887498945... \end{equation}

Implemente o cálculo da série de Fibonacci utilizando a expressão acima. Note que devido a erros de representação numérica (a raiz quadrada de 5 é um número irracional, com infinitas casas decimais, não representáveis no objeto Number do JavaScript básico), os resultados da série que utiliza a razão dourada não são inteiros (mas quase). Se aplicamos o critério usual de arredondamento para produzir um número inteiro com a série da razão dourada, vemos que os números realmente começam a divergir a partir do 71o., já muito perto do limite da capacidade tradicional de grandes números no JavaScript básico.

Console: i fibo1 fibo2 0 0 0 1 1 1 2 1 1 3 2 2 4 3 3.0000000000000004 5 5 5.000000000000001 6 8 8.000000000000002 ... 69 117669030460994 117669030460994.28 70 190392490709135 190392490709135.44 71 308061521170129 308061521170129.7 72 498454011879264 498454011879265.2 73 806515533049393 806515533049395 74 1304969544928657 1304969544928660 75 2111485077978050 2111485077978055.2 76 3416454622906707 3416454622906715.5 77 5527939700884757 5527939700884771 78 8944394323791464 8944394323791488
3. Modifique o programa anterior de modo que mostre não os números das duas sequências, mas a diferença entre eles.
Console: n, dif 0 0 1 0 2 0 3 0 4 -4.440892098500626e-16 5 -8.881784197001252e-16 6 -1.7763568394002505e-15 ... 69 -0.28125 70 -0.4375 71 -0.6875 72 -1.1875 73 -2 74 -3 75 -5.25 76 -8.5 77 -14 78 -24