notes.html

problem 20 · 57 lines

<article>
<h3>Problem Analysis</h3>
<p>
The task is to compute the sum of the decimal digits of <code>100!</code>. The
<a class="reference-source" href="https://en.wikipedia.org/wiki/Factorial" rel="noopener noreferrer" target="_blank">factorial</a>
of <code>n</code> is the product of all positive integers up to <code>n</code>, and the wrinkle is
purely one of scale: <code>100!</code> has 158 decimal digits, which vastly exceeds the roughly 19
digits a 64-bit integer can hold. The problem is therefore an exercise in
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a> —
computation on numbers larger than a native machine word, where the value is spread across many
storage cells rather than held in a single register.
</p>
<p>
The observation that makes this tractable is that we never need <code>n!</code> as an abstract
number — we only ever need its decimal digits. That reframes the work as two routine sub-tasks:
repeatedly multiply a large number by a small integer (at most 100), then add up the resulting
digits. Multiplying a <code>D</code>-digit number by a small scalar is ordinary
<a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplication_algorithm#Long_multiplication" rel="noopener noreferrer" target="_blank">long multiplication</a> —
walk each digit, multiply, propagate a carry — an <code>O(D)</code> pass. Doing this for every
factor from 2 to <code>n</code> gives <code>O(n · D(n))</code>, where <code>D(n)</code> is the digit
count of <code>n!</code>. By
<a class="reference-source" href="https://en.wikipedia.org/wiki/Stirling%27s_approximation" rel="noopener noreferrer" target="_blank">Stirling's approximation</a>
<code>D(n)</code> grows as <code>O(n log n)</code>, so the whole algorithm is about
<code>O(n² log n)</code> — utterly negligible at <code>n = 100</code>.
</p>
<h3>Solution Approach</h3>
<h4>Big-Integer Digit Array (C) and Built-in Arbitrary Precision (Python)</h4>
<p>
Both solutions (index 0) implement the same logical algorithm — form <code>n!</code>, then sum its
decimal digits — but they diverge entirely in how they represent the large number.
</p>
<p>
The C solution builds the big integer by hand. I store <code>n!</code> as a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
array of single decimal digits: <code>digits[0]</code> is the least significant digit,
<code>digits[1]</code> the next, and so on. I chose
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
ordering deliberately, because carry propagation runs from least significant to most significant —
the same direction as increasing array index — so the inner loop always walks forward. Starting
from 1, I multiply by each <code>i</code> from 2 to <code>n</code> using
<a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplication_algorithm#Long_multiplication" rel="noopener noreferrer" target="_blank">long multiplication</a>:
for each <code>i</code> I walk every occupied digit, compute <code>digits[j] * i + carry</code>,
store the result modulo 10, and carry the quotient forward; any carry remaining past the top digit
appends new positions one digit at a time. A final pass sums every digit. I sized the buffer at 512
digits, which comfortably covers the 158 digits of <code>100!</code>.
</p>
<p>
The Python solution is a single expression:
<code>sum(int(d) for d in str(math.factorial(n)))</code>. Python's <code>int</code> is
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>
natively, so <code>math.factorial</code> returns the exact value with no manual digit handling; I
convert it to a string and sum the integer value of each character. The representations differ
fundamentally: the C code works in base 10 throughout, whereas CPython stores the integer in a
binary internal form and converts to a decimal string only at the end.
</p>
</article>