notes.html

problem 16 · 74 lines

<article>
<h3>Problem Analysis</h3>
<p>
The task is to compute 2 raised to the 1000th power and sum the decimal digits of the result. The
mathematical content is modest, but the implementation challenge is real: 2^1000 has roughly
<code>ceil(1000 * log10(2)) = 302</code> decimal digits. That figure comes from the observation that
the number of base-10 digits of a positive integer <em>n</em> is <code>floor(log10(n)) + 1</code>,
and <code>log10(2^1000) = 1000 * log10(2)</code>. A 302-digit number dwarfs the capacity of any
native integer type in C, where even a 64-bit <code>unsigned long long</code> tops out near 19 decimal
digits. We therefore need
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>
- the ability to represent and manipulate integers whose size is bounded only by available memory.
</p>
<p>
The key observation that makes the problem tractable is that we only ever need the <em>decimal</em>
representation of the result, never its binary form. If we maintain the number as an array of base-10
digits throughout the computation, then extracting the digit sum at the end is a trivial linear pass.
The natural algorithm is repeated multiplication: start at 1 and multiply by the base <em>power</em>
times. Each multiplication is a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplication_algorithm#Long_multiplication" rel="noopener noreferrer" target="_blank">schoolbook (long) multiplication</a>
that walks across all current digits once, propagating a carry. With <em>P</em> multiplications over a
result of up to <em>D</em> digits (and <code>D ~ 0.301 * P</code>), the total cost is O(P * D) = O(P^2).
For P = 1000 that is about 300,000 digit operations - instantaneous on modern hardware.
</p>
<h3>Solution Approach</h3>
<h4>Algorithm 0 - Repeated decimal multiplication (C and Python)</h4>
<p>
Both files implement the same logical algorithm - compute <code>base^power</code> as an
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision integer</a>,
then sum its decimal digits - and differ only in how they realize that big integer.
</p>
<p>
<strong>Python version.</strong> Python integers carry
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>
built into the language, so I delegate the entire big-number problem to the runtime with the single
expression <code>base**power</code>. That one operator produces the full 302-digit value. I then convert
it to a string with <code>str(...)</code>, iterate over each character, convert each digit back to an
integer with <code>int(i)</code>, and feed the stream into <code>sum(...)</code>. The whole solve body is
one line: <code>sum((int(i) for i in str(base**power)))</code>. This is correct, idiomatic, and concise;
the cost is that I cede control of the internal representation to the interpreter, which here is
entirely acceptable.
</p>
<p>
<strong>C version.</strong> C has no native
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>,
so I built one by hand as an array of <code>unsigned char</code>, each element holding a single decimal
digit (0-9), with the least-significant digit at index 0 - a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
layout. The steps:
</p>
<ul>
<li><strong>Allocate.</strong> I compute an upper bound on the digit count as
      <code>(int)(power * 0.30103 + 10) + 10</code>, where 0.30103 approximates <code>log10(2)</code>,
      and call <code>calloc</code> to obtain a zero-initialized array. The size formula and the safety
      margin guarantee no reallocation is ever needed.</li>
<li><strong>Initialize.</strong> I set <code>digits[0] = 1</code> and <code>len = 1</code>, representing
      the value 1.</li>
<li><strong>Multiply.</strong> I loop <code>power</code> times, each iteration a
      <a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplication_algorithm#Long_multiplication" rel="noopener noreferrer" target="_blank">schoolbook (long) multiplication</a>
      by the base: I walk positions <code>j = 0..len-1</code>, computing
      <code>val = digits[j] * base + carry</code>, storing <code>val % 10</code> back, and carrying
      <code>val / 10</code> forward. After the digits are exhausted, any remaining carry is appended as
      new high-order digits via <code>digits[len++] = carry % 10</code> until the carry is consumed.</li>
<li><strong>Sum.</strong> A final linear pass accumulates all digits into a <code>long long</code>.</li>
</ul>
<p>
The crucial design decision is the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
digit order. Because carry propagates from the least-significant position upward - the same direction as
the loop - the array grows naturally at its high end with a simple append. A big-endian layout would
force either backward iteration or a final reversal, adding complexity for no benefit.
</p>
</article>