Skip to content

Commit 94c319f

Browse files
github-actions[bot]github-actions[bot]
committed
1 parent a3533e9 commit 94c319f

8 files changed

+239
-185
lines changed

‎1454/algebra/fibonacci-numbers.html

Lines changed: 60 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -6594,14 +6594,16 @@
65946594

65956595

65966596

6597-
6598-
65996597

66006598

66016599

66026600

66036601

66046602

6603+
6604+
6605+
6606+
66056607

66066608

66076609

@@ -6624,6 +6626,10 @@
66246626

66256627

66266628

6629+
6630+
6631+
6632+
66276633

66286634

66296635

@@ -6742,6 +6748,14 @@
67426748

67436749

67446750

6751+
6752+
6753+
6754+
6755+
6756+
6757+
6758+
67456759

67466760

67476761

@@ -6758,7 +6772,7 @@
67586772
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
67596773

67606774
Last update:
6761-
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="April 17, 2025 18:03:29">April 17, 2025</span>&emsp;
6775+
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="April 22, 2025 01:11:02">April 22, 2025</span>&emsp;
67626776

67636777
<!-- Tags -->
67646778

@@ -6795,7 +6809,9 @@ <h2 id="properties">Properties<a class="headerlink" href="#properties" title="Pe
67956809
<li>Cassini's identity:</li>
67966810
</ul>
67976811
<div class="arithmatex">$$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$</div>
6798-
<p>This can be proved by induction. A one-line proof due to Knuth comes from taking the determinant of the 2x2 matrix form below.</p>
6812+
<blockquote>
6813+
<p>This can be proved by induction. A one-line proof by Knuth comes from taking the determinant of the 2x2 matrix form below.</p>
6814+
</blockquote>
67996815
<ul>
68006816
<li>The "addition" rule:</li>
68016817
</ul>
@@ -6876,9 +6892,45 @@ <h3 id="fibonacci-in-linear-time">Fibonacci in linear time<a class="headerlink"
68766892
</code></pre></div>
68776893
<p>In this way, we obtain a linear solution, <span class="arithmatex">$O(n)$</span> time, saving all the values prior to <span class="arithmatex">$n$</span> in the sequence.</p>
68786894
<h3 id="matrix-form">Matrix form<a class="headerlink" href="#matrix-form" title="Permanent link">&para;</a></h3>
6879-
<p>It is easy to prove the following relation:</p>
6880-
<div class="arithmatex">$$\begin{pmatrix} 1 &amp; 1 \cr 1 &amp; 0 \cr\end{pmatrix} ^ n = \begin{pmatrix} F_{n+1} &amp; F_{n} \cr F_{n} &amp; F_{n-1} \cr\end{pmatrix}$$</div>
6881-
<p>Thus, in order to find <span class="arithmatex">$F_n$</span> in <span class="arithmatex">$O(log n)$</span> time, we must raise the matrix to n. (See <a href="binary-exp.html">Binary exponentiation</a>)</p>
6895+
<p>To go from <span class="arithmatex">$(F_n, F_{n-1})$</span> to <span class="arithmatex">$(F_{n+1}, F_n)$</span>, we can express the linear recurrence as a 2x2 matrix multiplication:</p>
6896+
<div class="arithmatex">$$
6897+
\begin{pmatrix}
6898+
1 &amp; 1 \\
6899+
1 &amp; 0
6900+
\end{pmatrix}
6901+
\begin{pmatrix}
6902+
F_n \\
6903+
F_{n-1}
6904+
\end{pmatrix}
6905+
=
6906+
\begin{pmatrix}
6907+
F_n + F_{n-1} \\
6908+
F_{n}
6909+
\end{pmatrix}
6910+
=
6911+
\begin{pmatrix}
6912+
F_{n+1} \\
6913+
F_{n}
6914+
\end{pmatrix}
6915+
$$</div>
6916+
<p>This lets us treat iterating the recurrence as repeated matrix multiplication, which has nice properties. In particular,</p>
6917+
<div class="arithmatex">$$
6918+
\begin{pmatrix}
6919+
1 &amp; 1 \\
6920+
1 &amp; 0
6921+
\end{pmatrix}^n
6922+
\begin{pmatrix}
6923+
F_1 \\
6924+
F_0
6925+
\end{pmatrix}
6926+
=
6927+
\begin{pmatrix}
6928+
F_{n+1} \\
6929+
F_{n}
6930+
\end{pmatrix}
6931+
$$</div>
6932+
<p>where <span class="arithmatex">$F_1 = 1, F_0 = 0$</span>.</p>
6933+
<p>Thus, in order to find <span class="arithmatex">$F_n$</span> in <span class="arithmatex">$O(\log n)$</span> time, we must raise the matrix to n. (See <a href="binary-exp.html">Binary exponentiation</a>)</p>
68826934
<div class="highlight"><pre><span></span><code><span class="k">struct</span><span class="w"> </span><span class="nc">matrix</span><span class="w"> </span><span class="p">{</span>
68836935
<span class="w"> </span><span class="kt">long</span><span class="w"> </span><span class="kt">long</span><span class="w"> </span><span class="n">mat</span><span class="p">[</span><span class="mi">2</span><span class="p">][</span><span class="mi">2</span><span class="p">];</span>
68846936
<span class="w"> </span><span class="n">matrix</span><span class="w"> </span><span class="k">friend</span><span class="w"> </span><span class="k">operator</span><span class="w"> </span><span class="o">*</span><span class="p">(</span><span class="k">const</span><span class="w"> </span><span class="n">matrix</span><span class="w"> </span><span class="o">&amp;</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="n">matrix</span><span class="w"> </span><span class="o">&amp;</span><span class="n">b</span><span class="p">){</span>
@@ -6982,7 +7034,7 @@ <h2 id="practice-problems">Practice Problems<a class="headerlink" href="#practic
69827034

69837035
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
69847036
<span class="contributors-text">Contributors:</span>
6985-
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/gabrielsimoes" title="gabrielsimoes" data-bi-name="contributorprofile" target="_blank">gabrielsimoes</a> (28.63%)</li><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (25.31%)</li><li><a href="#" title="Carlos Javier Blanco" data-bi-name="contributorprofile" target="_blank">Carlos Javier Blanco</a> (20.33%)</li><li><a href="https://github.com/madhur4127" title="madhur4127" data-bi-name="contributorprofile" target="_blank">madhur4127</a> (7.47%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (6.22%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (2.49%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (2.49%)</li><li><a href="https://github.com/md-shamim-ahmad" title="md-shamim-ahmad" data-bi-name="contributorprofile" target="_blank">md-shamim-ahmad</a> (2.07%)</li><li><a href="https://github.com/boxlesscat" title="boxlesscat" data-bi-name="contributorprofile" target="_blank">boxlesscat</a> (1.24%)</li><li><a href="https://github.com/yeetholmes619" title="yeetholmes619" data-bi-name="contributorprofile" target="_blank">yeetholmes619</a> (1.24%)</li><li><a href="https://github.com/jxu" title="jxu" data-bi-name="contributorprofile" target="_blank">jxu</a> (0.83%)</li><li><a href="https://github.com/pasthec" title="pasthec" data-bi-name="contributorprofile" target="_blank">pasthec</a> (0.83%)</li><li><a href="https://github.com/conlacda" title="conlacda" data-bi-name="contributorprofile" target="_blank">conlacda</a> (0.41%)</li><li><a href="https://github.com/ankit-kumar-dwivedi" title="ankit-kumar-dwivedi" data-bi-name="contributorprofile" target="_blank">ankit-kumar-dwivedi</a> (0.41%)</li></ul>
7037+
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/gabrielsimoes" title="gabrielsimoes" data-bi-name="contributorprofile" target="_blank">gabrielsimoes</a> (24.64%)</li><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (21.43%)</li><li><a href="#" title="Carlos Javier Blanco" data-bi-name="contributorprofile" target="_blank">Carlos Javier Blanco</a> (16.43%)</li><li><a href="https://github.com/jxu" title="jxu" data-bi-name="contributorprofile" target="_blank">jxu</a> (15.36%)</li><li><a href="https://github.com/madhur4127" title="madhur4127" data-bi-name="contributorprofile" target="_blank">madhur4127</a> (6.43%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (5.36%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (2.5%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (2.14%)</li><li><a href="https://github.com/md-shamim-ahmad" title="md-shamim-ahmad" data-bi-name="contributorprofile" target="_blank">md-shamim-ahmad</a> (1.79%)</li><li><a href="https://github.com/boxlesscat" title="boxlesscat" data-bi-name="contributorprofile" target="_blank">boxlesscat</a> (1.07%)</li><li><a href="https://github.com/yeetholmes619" title="yeetholmes619" data-bi-name="contributorprofile" target="_blank">yeetholmes619</a> (1.07%)</li><li><a href="https://github.com/pasthec" title="pasthec" data-bi-name="contributorprofile" target="_blank">pasthec</a> (0.71%)</li><li><a href="https://github.com/mhayter" title="mhayter" data-bi-name="contributorprofile" target="_blank">mhayter</a> (0.36%)</li><li><a href="https://github.com/conlacda" title="conlacda" data-bi-name="contributorprofile" target="_blank">conlacda</a> (0.36%)</li><li><a href="https://github.com/ankit-kumar-dwivedi" title="ankit-kumar-dwivedi" data-bi-name="contributorprofile" target="_blank">ankit-kumar-dwivedi</a> (0.36%)</li></ul>
69867038
</ul>
69877039

69887040
</article>

‎1454/feed_json_updated.json

Lines changed: 1 addition & 1 deletion
Large diffs are not rendered by default.

0 commit comments

Comments
 (0)