Problem Analysis
I need to extract the first one hundred decimal digits of the square root of every non-perfect-square integer in a range, sum those digits, and total the sums. The mathematical foundation is that the square root of a natural number is either an integer or an irrational number: a quantity that cannot be written as a ratio of two integers and whose decimal expansion neither terminates nor settles into a repeating cycle. So for every number that is not a perfect square, I have an unending string of digits and must read off a fixed prefix from it without rounding error contaminating my answer.
The observation that makes this tractable is a scaling trick. If x = sqrt(n), then x * 10^d = sqrt(n * 10^(2d)). The integer part of sqrt(n * 10^(2d)) is therefore exactly the first d significant digits of sqrt(n) written without a decimal point. This converts a problem about real-number precision into a pure integer square root problem: compute floor(sqrt(n * 10^(2d))). For n up to 999 and d = 100, the scaled value has roughly 206 decimal digits - far beyond the 64-bit range - so I need arbitrary-precision arithmetic (big integers). The cost of each big-integer multiply or divide grows with the digit count d, so the overall complexity is roughly O(N * d^2), where N is the count of irrational roots: the d^2 comes from schoolbook multiplication of two d-digit numbers, and the choice of root-finding algorithm controls how many such operations I perform per number.
Solution Approach
Heron's (Newton's) Method for Integer Square Root
Both p0080_s0.py and p0080_s0_c compute the integer square root using
Heron's method,
which is Newton's method
applied to the equation x^2 - S = 0. The iteration is x_new = (x + S / x) / 2. Each step roughly
doubles the number of correct digits, so the method converges
quadratically:
about seven iterations suffice to reach 100 digits.
- Scale the input to S = n * 10^(2d) using big integers.
- Pick a starting guess at or above the true root, so the sequence decreases monotonically
toward floor(sqrt(S)). In Python I seed with x = S itself, which is always a valid
overestimate for S >= 1; the quadratic convergence quickly absorbs the loose start. In C I
bootstrap with a double-precision estimate
sqrt(n) * 1e15(accurate to about 15 digits), add a margin of 100, then scale up by 10^(d-15) to land within a few iterations of the answer. - Iterate until x_new is no longer strictly less than x; that fixed point is floor(sqrt(S)).
- Stringify the result, take the first d characters, and sum their digits.
The Python version is almost a direct transcription of the math, using the walrus operator to assign the next iterate and compare it to the previous value in one expression. The C version is far larger because Heron's method requires big-integer division, which I implemented with Knuth's Algorithm D (long division on limb arrays, with divisor normalization and a two-step quotient-digit correction). This is the most intricate routine in the file and the reason the C solution earns its speed.
Binary Search for Integer Square Root
Both p0080_s1.py and p0080_s1_c find floor(sqrt(S)) by
binary search.
The invariant is low^2 <= S < high^2. Each step computes mid = (low + high) / 2, squares it, and
moves low or high according to whether mid^2 <= S. When high - low == 1, low is the answer.
Binary search
is conceptually simpler than Heron's method
- it needs only multiplication, never division - but it converges only
linearly:
it takes about log2(sqrt(S)) iterations, roughly 166 squarings of a 100-digit number for d = 100.
That is fine in Python but markedly slower in C. The C version adds a helper
bi_diff_is_one that tests the termination condition high - low == 1 directly,
avoiding a full subtraction allocation each iteration. Both versions start with low = 0 and
high = S, a maximally loose but always-correct bracket.