Skip to content

Instantly share code, notes, and snippets.

@mizar

mizar/fibonacci.ipynb

Last active February 6, 2025 04:00
Show Gist options
  • Save mizar/bb83bc050b6bdf9233d3eb1bd02799fd to your computer and use it in GitHub Desktop.
Save mizar/bb83bc050b6bdf9233d3eb1bd02799fd to your computer and use it in GitHub Desktop.
Download ZIP
fibonacci.ipynb
Display the source blob
Display the rendered blob
Raw
fibonacci.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"provenance": [],
"authorship_tag": "ABX9TyNR2znEQf/ko5GHPRidokiq",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/mizar/bb83bc050b6bdf9233d3eb1bd02799fd/fibonacci.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"source": [
"$$\n",
"\\begin{align*}\n",
"\\mathrm{Fib}(0)&=0\\\\\n",
"\\mathrm{Fib}(1)&=1\\\\\n",
"\\mathrm{Fib}(n)&=\\mathrm{Fib}(n-1)+\\mathrm{Fib}(n-2)\\\\\n",
"\\mathrm{Fib}(-n)&=\\begin{cases}-\\mathrm{Fib}(n)&n\\equiv 0\\ (\\mathrm{mod}\\mathrel{}2)\\\\ \\mathrm{Fib}(n)&n\\equiv 1\\ (\\mathrm{mod}\\mathrel{}2)\\end{cases}\\\\\n",
"\\begin{pmatrix}\\mathrm{Fib}(n+1)&\\mathrm{Fib}(n)\\\\ \\mathrm{Fib}(n)&\\mathrm{Fib}(n-1)\\end{pmatrix}&=\\begin{pmatrix}1&1\\\\ 1&0\\end{pmatrix}^n\\\\\n",
"\\begin{pmatrix}\\mathrm{Fib}(2n+1)&\\mathrm{Fib}(2n)\\\\ \\mathrm{Fib}(2n)&\\mathrm{Fib}(2n-1)\\end{pmatrix}&=\\begin{pmatrix}\\mathrm{Fib}(n+1)&\\mathrm{Fib}(n)\\\\ \\mathrm{Fib}(n)&\\mathrm{Fib}(n-1)\\end{pmatrix}^2\\\\\n",
"(a_n,b_n)&=(\\mathrm{Fib}(\\lfloor n/2\\rfloor), \\mathrm{Fib}(\\lfloor n/2\\rfloor+1))\\\\\n",
"(\\mathrm{Fib}(n),\\mathrm{Fib}(n+1))&=\\begin{cases}(0,1)&n=0\\\\ (1,0)&n=-1\\\\(2a_nb_n-a_n^2,\\ a_n^2+b_n^2)&n\\equiv 0\\ (\\mathrm{mod}\\mathrel{}2)\\\\ (a_n^2+b_n^2,\\ 2a_nb_n+b_n^2)&n\\equiv 1\\ (\\mathrm{mod}\\mathrel{}2)\\end{cases}\\\\\n",
"\\end{align*}\n",
"$$"
],
"metadata": {
"id": "RMLB8PP3gAa4"
}
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "joYE6G0bPifY",
"outputId": "f819448d-837a-4a21-f631-9ca160232737"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"0 (0, 1) (0, 1) 0 0\n",
"1 (1, 1) (1, 0) 1 1\n",
"2 (1, 2) (-1, 1) 1 -1\n",
"3 (2, 3) (2, -1) 2 2\n",
"4 (3, 5) (-3, 2) 3 -3\n",
"5 (5, 8) (5, -3) 5 5\n",
"6 (8, 13) (-8, 5) 8 -8\n",
"7 (13, 21) (13, -8) 13 13\n",
"8 (21, 34) (-21, 13) 21 -21\n",
"9 (34, 55) (34, -21) 34 34\n",
"10 (55, 89) (-55, 34) 55 -55\n",
"11 (89, 144) (89, -55) 89 89\n",
"12 (144, 233) (-144, 89) 144 -144\n",
"13 (233, 377) (233, -144) 233 233\n",
"14 (377, 610) (-377, 233) 377 -377\n",
"15 (610, 987) (610, -377) 610 610\n",
"16 (987, 1597) (-987, 610) 987 -987\n",
"17 (1597, 2584) (1597, -987) 1597 1597\n",
"18 (2584, 4181) (-2584, 1597) 2584 -2584\n",
"19 (4181, 6765) (4181, -2584) 4181 4181\n",
"20 (6765, 10946) (-6765, 4181) 6765 -6765\n",
"21 (10946, 17711) (10946, -6765) 10946 10946\n",
"22 (17711, 28657) (-17711, 10946) 17711 -17711\n",
"23 (28657, 46368) (28657, -17711) 28657 28657\n",
"24 (46368, 75025) (-46368, 28657) 46368 -46368\n",
"25 (75025, 121393) (75025, -46368) 75025 75025\n",
"26 (121393, 196418) (-121393, 75025) 121393 -121393\n",
"27 (196418, 317811) (196418, -121393) 196418 196418\n",
"28 (317811, 514229) (-317811, 196418) 317811 -317811\n",
"29 (514229, 832040) (514229, -317811) 514229 514229\n",
"30 (832040, 1346269) (-832040, 514229) 832040 -832040\n",
"31 (1346269, 2178309) (1346269, -832040) 1346269 1346269\n",
"32 (2178309, 3524578) (-2178309, 1346269) 2178309 -2178309\n",
"33 (3524578, 5702887) (3524578, -2178309) 3524578 3524578\n",
"34 (5702887, 9227465) (-5702887, 3524578) 5702887 -5702887\n",
"35 (9227465, 14930352) (9227465, -5702887) 9227465 9227465\n",
"36 (14930352, 24157817) (-14930352, 9227465) 14930352 -14930352\n",
"37 (24157817, 39088169) (24157817, -14930352) 24157817 24157817\n",
"38 (39088169, 63245986) (-39088169, 24157817) 39088169 -39088169\n",
"39 (63245986, 102334155) (63245986, -39088169) 63245986 63245986\n",
"40 (102334155, 165580141) (-102334155, 63245986) 102334155 -102334155\n",
"41 (165580141, 267914296) (165580141, -102334155) 165580141 165580141\n",
"42 (267914296, 433494437) (-267914296, 165580141) 267914296 -267914296\n",
"43 (433494437, 701408733) (433494437, -267914296) 433494437 433494437\n",
"44 (701408733, 1134903170) (-701408733, 433494437) 701408733 -701408733\n",
"45 (1134903170, 1836311903) (1134903170, -701408733) 1134903170 1134903170\n",
"46 (1836311903, 2971215073) (-1836311903, 1134903170) 1836311903 -1836311903\n",
"47 (2971215073, 4807526976) (2971215073, -1836311903) 2971215073 2971215073\n",
"48 (4807526976, 7778742049) (-4807526976, 2971215073) 4807526976 -4807526976\n",
"49 (7778742049, 12586269025) (7778742049, -4807526976) 7778742049 7778742049\n",
"50 (12586269025, 20365011074) (-12586269025, 7778742049) 12586269025 -12586269025\n",
"51 (20365011074, 32951280099) (20365011074, -12586269025) 20365011074 20365011074\n",
"52 (32951280099, 53316291173) (-32951280099, 20365011074) 32951280099 -32951280099\n",
"53 (53316291173, 86267571272) (53316291173, -32951280099) 53316291173 53316291173\n",
"54 (86267571272, 139583862445) (-86267571272, 53316291173) 86267571272 -86267571272\n",
"55 (139583862445, 225851433717) (139583862445, -86267571272) 139583862445 139583862445\n",
"56 (225851433717, 365435296162) (-225851433717, 139583862445) 225851433717 -225851433717\n",
"57 (365435296162, 591286729879) (365435296162, -225851433717) 365435296162 365435296162\n",
"58 (591286729879, 956722026041) (-591286729879, 365435296162) 591286729879 -591286729879\n",
"59 (956722026041, 1548008755920) (956722026041, -591286729879) 956722026041 956722026041\n",
"60 (1548008755920, 2504730781961) (-1548008755920, 956722026041) 1548008755920 -1548008755920\n",
"61 (2504730781961, 4052739537881) (2504730781961, -1548008755920) 2504730781961 2504730781961\n",
"62 (4052739537881, 6557470319842) (-4052739537881, 2504730781961) 4052739537881 -4052739537881\n",
"63 (6557470319842, 10610209857723) (6557470319842, -4052739537881) 6557470319842 6557470319842\n",
"64 (10610209857723, 17167680177565) (-10610209857723, 6557470319842) 10610209857723 -10610209857723\n",
"65 (17167680177565, 27777890035288) (17167680177565, -10610209857723) 17167680177565 17167680177565\n",
"66 (27777890035288, 44945570212853) (-27777890035288, 17167680177565) 27777890035288 -27777890035288\n",
"67 (44945570212853, 72723460248141) (44945570212853, -27777890035288) 44945570212853 44945570212853\n",
"68 (72723460248141, 117669030460994) (-72723460248141, 44945570212853) 72723460248141 -72723460248141\n",
"69 (117669030460994, 190392490709135) (117669030460994, -72723460248141) 117669030460994 117669030460994\n",
"70 (190392490709135, 308061521170129) (-190392490709135, 117669030460994) 190392490709135 -190392490709135\n",
"71 (308061521170129, 498454011879264) (308061521170129, -190392490709135) 308061521170129 308061521170129\n",
"72 (498454011879264, 806515533049393) (-498454011879264, 308061521170129) 498454011879264 -498454011879264\n",
"73 (806515533049393, 1304969544928657) (806515533049393, -498454011879264) 806515533049393 806515533049393\n",
"74 (1304969544928657, 2111485077978050) (-1304969544928657, 806515533049393) 1304969544928657 -1304969544928657\n",
"75 (2111485077978050, 3416454622906707) (2111485077978050, -1304969544928657) 2111485077978050 2111485077978050\n",
"76 (3416454622906707, 5527939700884757) (-3416454622906707, 2111485077978050) 3416454622906707 -3416454622906707\n",
"77 (5527939700884757, 8944394323791464) (5527939700884757, -3416454622906707) 5527939700884757 5527939700884757\n",
"78 (8944394323791464, 14472334024676221) (-8944394323791464, 5527939700884757) 8944394323791464 -8944394323791464\n",
"79 (14472334024676221, 23416728348467685) (14472334024676221, -8944394323791464) 14472334024676221 14472334024676221\n",
"80 (23416728348467685, 37889062373143906) (-23416728348467685, 14472334024676221) 23416728348467685 -23416728348467685\n",
"81 (37889062373143906, 61305790721611591) (37889062373143906, -23416728348467685) 37889062373143906 37889062373143906\n",
"82 (61305790721611591, 99194853094755497) (-61305790721611591, 37889062373143906) 61305790721611591 -61305790721611591\n",
"83 (99194853094755497, 160500643816367088) (99194853094755497, -61305790721611591) 99194853094755497 99194853094755497\n",
"84 (160500643816367088, 259695496911122585) (-160500643816367088, 99194853094755497) 160500643816367088 -160500643816367088\n",
"85 (259695496911122585, 420196140727489673) (259695496911122585, -160500643816367088) 259695496911122585 259695496911122585\n",
"86 (420196140727489673, 679891637638612258) (-420196140727489673, 259695496911122585) 420196140727489673 -420196140727489673\n",
"87 (679891637638612258, 1100087778366101931) (679891637638612258, -420196140727489673) 679891637638612258 679891637638612258\n",
"88 (1100087778366101931, 1779979416004714189) (-1100087778366101931, 679891637638612258) 1100087778366101931 -1100087778366101931\n",
"89 (1779979416004714189, 2880067194370816120) (1779979416004714189, -1100087778366101931) 1779979416004714189 1779979416004714189\n",
"90 (2880067194370816120, 4660046610375530309) (-2880067194370816120, 1779979416004714189) 2880067194370816120 -2880067194370816120\n",
"91 (4660046610375530309, 7540113804746346429) (4660046610375530309, -2880067194370816120) 4660046610375530309 4660046610375530309\n",
"92 (7540113804746346429, 12200160415121876738) (-7540113804746346429, 4660046610375530309) 7540113804746346429 -7540113804746346429\n",
"93 (12200160415121876738, 19740274219868223167) (12200160415121876738, -7540113804746346429) 12200160415121876738 12200160415121876738\n",
"94 (19740274219868223167, 31940434634990099905) (-19740274219868223167, 12200160415121876738) 19740274219868223167 -19740274219868223167\n",
"95 (31940434634990099905, 51680708854858323072) (31940434634990099905, -19740274219868223167) 31940434634990099905 31940434634990099905\n",
"96 (51680708854858323072, 83621143489848422977) (-51680708854858323072, 31940434634990099905) 51680708854858323072 -51680708854858323072\n",
"97 (83621143489848422977, 135301852344706746049) (83621143489848422977, -51680708854858323072) 83621143489848422977 83621143489848422977\n",
"98 (135301852344706746049, 218922995834555169026) (-135301852344706746049, 83621143489848422977) 135301852344706746049 -135301852344706746049\n",
"99 (218922995834555169026, 354224848179261915075) (218922995834555169026, -135301852344706746049) 218922995834555169026 218922995834555169026\n",
"100 (354224848179261915075, 573147844013817084101) (-354224848179261915075, 218922995834555169026) 354224848179261915075 -354224848179261915075\n",
"101 (573147844013817084101, 927372692193078999176) (573147844013817084101, -354224848179261915075) 573147844013817084101 573147844013817084101\n",
"102 (927372692193078999176, 1500520536206896083277) (-927372692193078999176, 573147844013817084101) 927372692193078999176 -927372692193078999176\n",
"103 (1500520536206896083277, 2427893228399975082453) (1500520536206896083277, -927372692193078999176) 1500520536206896083277 1500520536206896083277\n",
"104 (2427893228399975082453, 3928413764606871165730) (-2427893228399975082453, 1500520536206896083277) 2427893228399975082453 -2427893228399975082453\n",
"105 (3928413764606871165730, 6356306993006846248183) (3928413764606871165730, -2427893228399975082453) 3928413764606871165730 3928413764606871165730\n",
"106 (6356306993006846248183, 10284720757613717413913) (-6356306993006846248183, 3928413764606871165730) 6356306993006846248183 -6356306993006846248183\n",
"107 (10284720757613717413913, 16641027750620563662096) (10284720757613717413913, -6356306993006846248183) 10284720757613717413913 10284720757613717413913\n",
"108 (16641027750620563662096, 26925748508234281076009) (-16641027750620563662096, 10284720757613717413913) 16641027750620563662096 -16641027750620563662096\n",
"109 (26925748508234281076009, 43566776258854844738105) (26925748508234281076009, -16641027750620563662096) 26925748508234281076009 26925748508234281076009\n",
"110 (43566776258854844738105, 70492524767089125814114) (-43566776258854844738105, 26925748508234281076009) 43566776258854844738105 -43566776258854844738105\n",
"111 (70492524767089125814114, 114059301025943970552219) (70492524767089125814114, -43566776258854844738105) 70492524767089125814114 70492524767089125814114\n",
"112 (114059301025943970552219, 184551825793033096366333) (-114059301025943970552219, 70492524767089125814114) 114059301025943970552219 -114059301025943970552219\n",
"113 (184551825793033096366333, 298611126818977066918552) (184551825793033096366333, -114059301025943970552219) 184551825793033096366333 184551825793033096366333\n",
"114 (298611126818977066918552, 483162952612010163284885) (-298611126818977066918552, 184551825793033096366333) 298611126818977066918552 -298611126818977066918552\n",
"115 (483162952612010163284885, 781774079430987230203437) (483162952612010163284885, -298611126818977066918552) 483162952612010163284885 483162952612010163284885\n",
"116 (781774079430987230203437, 1264937032042997393488322) (-781774079430987230203437, 483162952612010163284885) 781774079430987230203437 -781774079430987230203437\n",
"117 (1264937032042997393488322, 2046711111473984623691759) (1264937032042997393488322, -781774079430987230203437) 1264937032042997393488322 1264937032042997393488322\n",
"118 (2046711111473984623691759, 3311648143516982017180081) (-2046711111473984623691759, 1264937032042997393488322) 2046711111473984623691759 -2046711111473984623691759\n",
"119 (3311648143516982017180081, 5358359254990966640871840) (3311648143516982017180081, -2046711111473984623691759) 3311648143516982017180081 3311648143516982017180081\n",
"120 (5358359254990966640871840, 8670007398507948658051921) (-5358359254990966640871840, 3311648143516982017180081) 5358359254990966640871840 -5358359254990966640871840\n",
"121 (8670007398507948658051921, 14028366653498915298923761) (8670007398507948658051921, -5358359254990966640871840) 8670007398507948658051921 8670007398507948658051921\n",
"122 (14028366653498915298923761, 22698374052006863956975682) (-14028366653498915298923761, 8670007398507948658051921) 14028366653498915298923761 -14028366653498915298923761\n",
"123 (22698374052006863956975682, 36726740705505779255899443) (22698374052006863956975682, -14028366653498915298923761) 22698374052006863956975682 22698374052006863956975682\n",
"124 (36726740705505779255899443, 59425114757512643212875125) (-36726740705505779255899443, 22698374052006863956975682) 36726740705505779255899443 -36726740705505779255899443\n",
"125 (59425114757512643212875125, 96151855463018422468774568) (59425114757512643212875125, -36726740705505779255899443) 59425114757512643212875125 59425114757512643212875125\n",
"126 (96151855463018422468774568, 155576970220531065681649693) (-96151855463018422468774568, 59425114757512643212875125) 96151855463018422468774568 -96151855463018422468774568\n",
"127 (155576970220531065681649693, 251728825683549488150424261) (155576970220531065681649693, -96151855463018422468774568) 155576970220531065681649693 155576970220531065681649693\n",
"128 (251728825683549488150424261, 407305795904080553832073954) (-251728825683549488150424261, 155576970220531065681649693) 251728825683549488150424261 -251728825683549488150424261\n"
]
}
],
"source": [
"import functools\n",
"\n",
"@functools.lru_cache\n",
"def fib_pair(n: int) -> tuple[int, int]:\n",
" \"\"\"return (fibonacci(n), fibonacci(n+1)) \"\"\"\n",
" assert isinstance(n, int)\n",
" if n == 0:\n",
" return (0, 1)\n",
" elif n == -1:\n",
" return (1, 0)\n",
" elif (n & 1) == 0:\n",
" a, b = fib_pair(n >> 1)\n",
" return ((2 * b - a) * a, a * a + b * b)\n",
" else:\n",
" a, b = fib_pair(n >> 1)\n",
" return (a * a + b * b, (2 * a + b) * b)\n",
"def fibonacci(n: int) -> int:\n",
" \"\"\"return fibonacci(n)\"\"\"\n",
" assert isinstance(n, int)\n",
" return fib_pair(n)[0]\n",
"\n",
"for n in range(129):\n",
" print(n, fib_pair(n), fib_pair(-n), fibonacci(n), fibonacci(-n))\n"
]
},
{
"cell_type": "markdown",
"source": [],
"metadata": {
"id": "Gyn1_DBof_bT"
}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment