notes.html

problem 99 · 25 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem asks me to compare one thousand numbers of the form <code>base^exponent</code> and identify which line holds the largest, where some of these numbers run to over three million digits. The naive approach - actually raising each base to its exponent and comparing the resulting integers - is hopeless: even with arbitrary-precision arithmetic, materializing a three-million-digit number takes substantial memory, and comparing two such numbers digit by digit is slow. The breakthrough is realizing that I do not need the values themselves, only their relative order. The <a class="reference-source" href="https://en.wikipedia.org/wiki/Logarithm" rel="noopener noreferrer" target="_blank">logarithm</a> is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Monotonic_function" rel="noopener noreferrer" target="_blank">strictly increasing function</a>, meaning that for any positive numbers <code>A</code> and <code>B</code>, the relation <code>A &gt; B</code> holds exactly when <code>log(A) &gt; log(B)</code>. Because the transform preserves ordering perfectly, ranking by logarithm gives the identical answer to ranking by the true values - with none of the cost.
</p>
<p>
Pairing this with the identity <code>log(b^e) = e * log(b)</code> collapses an intractable exponentiation into a single multiplication. To rank <code>b^e</code> I only need <code>e * log(b)</code>, an ordinary floating-point number comparable in constant time. The whole algorithm is therefore a single linear scan over the N = 1000 lines, doing one <a class="reference-source" href="https://en.wikipedia.org/wiki/Logarithm" rel="noopener noreferrer" target="_blank">logarithm</a> and one multiply per line while tracking the running maximum - an O(N) procedure with a tiny constant factor. The one thing I must verify is precision: a 64-bit <a class="reference-source" href="https://en.wikipedia.org/wiki/Double-precision_floating-point_format" rel="noopener noreferrer" target="_blank">double-precision float</a> carries roughly 15-16 significant decimal digits, far more than enough to separate 1000 distinct candidates whose log values differ well beyond rounding noise.
</p>
<h3>Solution Approach</h3>
<h4>Logarithmic Linear Scan (Python and C)</h4>
<p>
Both <code>p0099_s0.py</code> and <code>p0099_s0.c</code> implement the same algorithm; they differ only in language mechanics. The steps are:
</p>
<ul>
<li><strong>Read the file:</strong> A runner helper (<code>get_text_file</code>) resolves the resource locally and loads its contents into memory. Reading the whole 22K file at once is trivial and avoids per-line I/O overhead.</li>
<li><strong>Parse each line:</strong> Each line splits on the comma into an integer base and an integer exponent. Blank or malformed lines are skipped with a warning rather than aborting, which keeps the code robust to trailing newlines and Windows-style line endings.</li>
<li><strong>Compute the ranking value:</strong> For each pair I compute <code>log_val = exponent * log(base)</code>. By the identity <code>log(b^e) = e * log(b)</code>, this is exactly the <a class="reference-source" href="https://en.wikipedia.org/wiki/Logarithm" rel="noopener noreferrer" target="_blank">logarithm</a> of the full power - the surrogate that ranks identically to the real value.</li>
<li><strong>Track the argmax:</strong> Two state variables - the best value seen so far and the line that produced it - update whenever a larger value appears. This finds not merely the maximum but the line number achieving it, in a single pass.</li>
<li><strong>Return the 1-based line number:</strong> Since the answer is a line number, Python uses <code>enumerate(numbers, start=1)</code> and C maintains an explicit <code>line_num</code> counter.</li>
</ul>
<p>
The differences are purely mechanical. The Python version retains the winning base and exponent so a <code>--show</code> flag can print a human-readable summary, including an estimated digit count via <code>max_val / log(10)</code>. It uses <code>splitlines</code> to normalize line endings and a <code>try/except</code> block around parsing. The C version tokenizes the buffer with <code>strtok_r</code>, manually strips a trailing <code>\r</code>, splits on the comma with <code>strchr</code>, and parses each field with <code>atoll</code>. Both convert from integers to <code>double</code> only at the moment the logarithm is taken.
</p>
</article>