Problem Analysis
The Fibonacci sequence is defined by the recurrence relation F(n) = F(n-1) + F(n-2). A fundamental fact about this sequence is that it grows exponentially: F(n) is asymptotically proportional to phi^n, where phi = (1 + sqrt(5)) / 2 ≈ 1.618 is the golden ratio. Because the value grows exponentially, the number of decimal digits grows only linearly with the index n - roughly n * log10(phi) digits. This means reaching 1000 digits takes about 1000 / log10(phi) ≈ 4785 terms, so the loop is short. The real challenge is arithmetic precision: Fibonacci numbers exceed the range of a 64-bit integer after only about the 93rd term, so to reach 1000 digits we need arbitrary-precision arithmetic (big integers).
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 O(N * D), where N ≈ 4782 is the target index and D is the number of digit-groups (limbs) in each number - each addition touches every limb once, and there are N additions.
Solution Approach
Iterative Big-Integer Fibonacci (Python and C, index 0)
Both solutions share the same algorithm: start from F(1) = F(2) = 1, repeatedly apply (a, b) = (b, a + b), and stop as soon as b has at least n decimal digits. An index counter advances alongside the values, and its final value is the answer.
In Python the algorithm is almost trivial because the language has native big integers. I keep two variables a and b, both initialised to 1, and an index i = 2 pointing at b. The loop condition b < 10 ** (n - 1) exploits a clean threshold test: a number has at least n digits exactly when it is greater than or equal to 10**(n-1). Inside the loop, the parallel assignment a, b = b, a + b advances both values in one step. Python grows the integers automatically, so there is no manual memory management.
The C solution has no native big integer, so I hand-rolled a minimal one. I chose a base-109 limb representation: each entry of the limbs 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 9 * (len - 1) for the fully-packed lower limbs. This avoids a base conversion on every iteration. The base 109 is the largest power of ten that lets two limbs plus a carry fit comfortably inside a 64-bit accumulator without overflow. bigint_add walks both numbers from the least significant limb upward, propagating a carry exactly as in grade-school addition. I pre-allocated MAX_LIMBS = 200 limbs (1800 digits), far beyond the requirement, so no dynamic resizing is ever needed. The two live values are a and b, with a third tmp holding the sum before memcpy shuffles the values into place.