My square-root search returned 1073741823 for x = i32::MAX.
One line in the repo’s solution is the difference: let x = x as i64;. Take it out and the algorithm still reads like a correct solution, which is exactly what makes it dangerous. Everything around it is the textbook binary search: find the largest integer whose square is at most x, compare, move one bound, repeat.
The constraint is 0 <= x <= 2^31 - 1. The natural upper bound for the search is somewhere near x / 2, so mid climbs past a billion. Square a billion and you need about a quintillion, and i32 stops at 2147483647.
I ran the same search with the multiply left in i32, on x = i32::MAX. This is my own experiment; the algorithm is otherwise identical to the repo’s file:
let mut left: i32 = 1;
let mut right: i32 = x / 2;
while left <= right {
let mid = left + (right - left) / 2;
let square = mid * mid;
if square == x {
return mid as i32;
} else if square < x {
left = mid + 1;
} else {
right = mid - 1;
}
}
In the debug profile it dies on the first iteration:
attempt to multiply with overflow
In the release profile it does not die. It returns an answer.
step 30: left=1073741823 right=1073741823 mid=1073741823
square=-2147483647
fell through, right=1073741823
mid * mid wrapped to a negative number. A negative square compares as less than every positive x, so square < x is true and the search believes it is still below the answer. It walks left past the true answer, off the end of the search space, falls out of the loop, and returns right, which is 1073741823.
The correct answer is 46340.
That gap between 1073741823 and 46340 is the whole reason the cast is in the file.
Cast first, then search
Here is the repo’s solution in full:
pub fn my_sqrt(x: i32) -> i32 {
if x < 2 {
return x;
}
let x = x as i64;
let mut left: i64 = 1;
let mut right: i64 = x / 2;
while left <= right {
let mid = left + (right - left) / 2;
let square = mid * mid;
if square == x {
return mid as i32;
} else if square < x {
left = mid + 1;
} else {
right = mid - 1;
}
}
right as i32
}
x is promoted to i64 before the loop, and left and right are declared i64 so the comparison happens at the same width. The largest product this search can produce is 1152921502459363329. That is about eight times below i64::MAX, so the multiply cannot fail, and the comparison means what it says.
This is not defensive arithmetic. Widening does not stop a panic; it changes the program. A wrapped square is negative, and a negative square is smaller than every x in the problem’s range. Once the multiply can lie, the search is not searching for a square root anymore. It is walking a search space that no longer has the shape the algorithm assumes.
Rust gives you two different failure modes for the same line of code:
- Debug:
attempt to multiply with overflow, a panic, the process dies with a message that names the operation. - Release: wrapping multiplication, no diagnostic, a wrong number.
One of those is a bug report. The other is a wrong answer that reaches a user with nothing on the way out to say it was wrong. A language with only the second behavior would be miserable to debug. A language with only the first would be impossible to ship.
Both of them, and you pick per profile.
The midpoint is free insurance
The search also uses the overflow-safe midpoint:
let mid = left + (right - left) / 2;
I checked whether that form is load-bearing here. It is not. The search caps right at x / 2, and the loop keeps left <= right, so the largest sum the midpoint can ever form is 2147483646, exactly one below i32::MAX. I also ran the search with the naive (left + right) / 2, and again with right set to x instead of x / 2. Neither overflowed. Both returned 46340.
So in this file the safe midpoint is habit rather than protection. That is worth saying out loud, because a solution with two overflow sites and one cast has a hole in it, and knowing which site is load-bearing is the difference between a fix and a guess. Here the load-bearing part is one character wide: the i64 on the multiply. The midpoint is free insurance that happens not to be needed.
The tests pass either way
The repo’s tests for this file are:
for (x, res) in [(4, 2), (8, 2)] {
assert_eq!(Solution::my_sqrt(x), res);
}
I ran those exact cases against the un-widened i32 version. They pass. Both of them.
Neither 4 nor 8 can overflow a multiply, so the test suite has no opinion about the one decision that makes the solution correct. The bug lives entirely outside the range the tests cover, which is where overflow bugs live in general. A test that pins x = i32::MAX would have caught it in debug on the first run.
Nothing here allocates
The problem forbids built-in exponent functions, and the solution does not reach for f64::sqrt either, so there is no float round trip and no question about where rounding goes. There is no Vec, no String, no borrow of a slice, nothing to allocate. The whole computation is a handful of i64 values in registers.
The algorithm is arithmetic. When the arithmetic can lie, the type system is not decoration on top of it. It is the part that decides whether the arithmetic is allowed to be trusted.
The cast goes in before the search, not after it, and it goes from i32 to i64 rather than the other way around. That is the whole fix.
What I take from it is narrower than a rule: when a solution carries a widening cast, that cast is the first thing I pull out and run the tests against. Here they still passed without it, which is how the bug got in.
Next: Never Build the Number