notes.html
problem 25 · 21 lines
<article>
<h3>Problem Analysis</h3>
<p>
The <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci sequence</a> is defined by the <a class="reference-source" href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="noopener noreferrer" target="_blank">recurrence relation</a> <code>F(n) = F(n-1) + F(n-2)</code>. A fundamental fact about this sequence is that it grows exponentially: <code>F(n)</code> is asymptotically proportional to <code>phi^n</code>, where <code>phi = (1 + sqrt(5)) / 2 ≈ 1.618</code> is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Golden_ratio" rel="noopener noreferrer" target="_blank">golden ratio</a>. Because the value grows exponentially, the number of decimal digits grows only linearly with the index <code>n</code> - roughly <code>n * log10(phi)</code> digits. This means reaching 1000 digits takes about <code>1000 / log10(phi) ≈ 4785</code> terms, so the loop is short. The real challenge is arithmetic precision: <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci numbers</a> exceed the range of a 64-bit integer after only about the 93rd term, so to reach 1000 digits we need <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a> (<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">big integers</a>).
</p>
<p>
The observation that makes the problem tractable is that we never need the full sequence - only the two most recent terms suffice to compute the next. So memory is constant in the number of live big integers (just two or three). Likewise, checking whether a number has reached 1000 digits does not require fully expanding it: we can compare against a power of ten, or inspect only the most significant chunk of a decimal representation. The overall complexity is <code>O(N * D)</code>, where <code>N ≈ 4782</code> is the target index and <code>D</code> is the number of digit-groups (limbs) in each number - each addition touches every limb once, and there are <code>N</code> additions.
</p>
<h3>Solution Approach</h3>
<h4>Iterative <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">Big-Integer</a> <a class="reference-source" href="https://en.wikipedia.org/wiki/Fibonacci_sequence" rel="noopener noreferrer" target="_blank">Fibonacci</a> (Python and C, index 0)</h4>
<p>
Both solutions share the same algorithm: start from <code>F(1) = F(2) = 1</code>, repeatedly apply <code>(a, b) = (b, a + b)</code>, and stop as soon as <code>b</code> has at least <code>n</code> decimal digits. An index counter advances alongside the values, and its final value is the answer.
</p>
<p>
In Python the algorithm is almost trivial because the language has native <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">big integers</a>. I keep two variables <code>a</code> and <code>b</code>, both initialised to 1, and an index <code>i = 2</code> pointing at <code>b</code>. The loop condition <code>b < 10 ** (n - 1)</code> exploits a clean threshold test: a number has at least <code>n</code> digits exactly when it is greater than or equal to <code>10**(n-1)</code>. Inside the loop, the <a class="reference-source" href="https://en.wikipedia.org/wiki/Assignment_(computer_science)#Parallel_assignment" rel="noopener noreferrer" target="_blank">parallel assignment</a> <code>a, b = b, a + b</code> advances both values in one step. Python grows the integers automatically, so there is no manual memory management.
</p>
<p>
The C solution has no native <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">big integer</a>, so I hand-rolled a minimal one. I chose a <strong>base-10<sup>9</sup> limb</strong> representation: each entry of the <code>limbs</code> array holds up to 9 decimal digits packed into a 64-bit unsigned integer. I picked a decimal base rather than a binary one specifically because the problem asks about decimal digits - with decimal limbs, counting digits requires inspecting only the top limb (counting its digits by repeated division by 10) and adding <code>9 * (len - 1)</code> for the fully-packed lower limbs. This avoids a base conversion on every iteration. The base 10<sup>9</sup> is the largest power of ten that lets two limbs plus a carry fit comfortably inside a 64-bit accumulator without overflow. <code>bigint_add</code> walks both numbers from the least significant limb upward, propagating a carry exactly as in grade-school addition. I pre-allocated <code>MAX_LIMBS = 200</code> limbs (1800 digits), far beyond the requirement, so no dynamic resizing is ever needed. The two live values are <code>a</code> and <code>b</code>, with a third <code>tmp</code> holding the sum before <code>memcpy</code> shuffles the values into place.
</p>
</article>