cint university / 401 / ced, the cint editor
401-02: hunting an overflow
This is lab 401-02 of CU-401.2, checked against cint 0.2.0.
You will summarize a month of temperature readings until a sum overflows two calls below main. Then you will find the reading where it broke and try three fixes. An exact check will show that the program's first output was wrong.
Take it after 201-09. It uses the method of 201-07 from start to end.
the program
A sensor sends a temperature once a minute, in hundredths of a degree Celsius, and the program reports each day's low, high, mean and spread. The spread is the standard deviation: the square root of the mean of the squared distances from the mean.
// weather.ci: a month of temperature readings, one a minute,
// summarized day by day. A reading is in hundredths of a degree
// Celsius, as the sensor sends it.
const I64 DAYS = 30;
const I64 PER_DAY = 1_440;
// The reading at minute m of day d. It stands in for a file of real
// readings: a base that warms a little each day, a daily swing that
// peaks at 2 PM and a small, repeatable wobble.
I32 reading(I64 d, I64 m) {
I64 base = 400 + 60 * d;
I64 from_peak = m - 840;
if (from_peak < 0) {
from_peak = -from_peak;
}
I64 swing = 600 - from_peak * 600 / 720;
I64 wobble = (d * PER_DAY + m) * 7_919 % 61 - 30;
return (base + swing + wobble) as I32;
}
I32 sum_of_squares[n](in I32[n] xs) {
I32 total = 0;
for i in 0..n {
total += xs[i] * xs[i];
}
return total;
}
void summarize(I64 d) {
I32[1_440] day;
I32 low = I32.max;
I32 high = I32.min;
I32 total = 0;
for m in 0..PER_DAY {
day[m] = reading(d, m);
if (day[m] < low) {
low = day[m];
}
if (day[m] > high) {
high = day[m];
}
total += day[m];
}
I32 mean = total / 1_440;
I32 variance = sum_of_squares(day) / 1_440 - mean * mean;
I32 spread = isqrt(variance);
"day {d:>2}: low {low:/100}, high {high:/100}, mean {mean:/100}, spread {spread:/100}\n";
}
void main() {
for d in 1..=DAYS {
summarize(d);
}
}
variance uses the formula from statistics books: the mean of the squares, less the square of the mean.
step 1: run it, and keep what it printed
$ cint run weather.ci > golden.txt
fault[E_OVERFLOW]: the exact result is outside the type's range
--> weather.ci:25:15
|
25 | total += xs[i] * xs[i];
| ^ add.checked.i32
|
= operation: add.checked.i32
= operand-count: 2
= operand: I32 2146711192
= operand: I32 1201216
= exact: 2147912408
= limit: I32 2147483647
= revision: c92d9c049c47774f269b91122ebc997629c7f7b431d5bd0b41b36a292759d57f
= source-map: none
= address: none
= stack-depth: 2
= called from: weather.ci:53:9
= called from: weather.ci:46:20
= fuel-consumed: 38831 (not part of the fault record)
= state: the program stopped; stdout holds what it wrote before the fault
$ cat golden.txt
day 1: low 3.40, high 10.84, mean 7.52, spread 1.87
day 2: low 4.00, high 11.42, mean 8.12, spread 1.87
day 3: low 4.60, high 12.07, mean 8.72, spread 1.87
day 4: low 5.19, high 12.63, mean 9.32, spread 1.87
day 5: low 5.79, high 13.30, mean 9.91, spread 1.93
day 6: low 6.39, high 13.86, mean 10.52, spread 1.87
day 7: low 6.98, high 14.42, mean 11.12, spread 1.88
day 8: low 7.58, high 15.09, mean 11.71, spread 1.93
A golden should be checked by hand before it is saved. The lows, highs and means are easy to check against reading. The spreads are not, so this lab saves them unchecked, to show what that costs.
step 2: read the call stack
The report names three places, from the outside in:
called from: weather.ci:53:9issummarize(d);inmain.called from: weather.ci:46:20is the call tosum_of_squaresinsummarize.--> weather.ci:25:15is the+=insidesum_of_squares, where the fault happened.
stack-depth: 2 counts the two calls below main. The output stops after day 8, so the fault came while summarizing day 9. The first operand is the running total of squares, 2146711192, and the second is one more square, 1201216, which is 1096 × 1096. Together they pass the largest I32, 2147483647.
step 3: locate the reading
The report says which addition broke, but not at which minute. cint debug locate replays the run and shows the operations before the fault:
$ cint debug locate weather.ci --save-case hot.case
program weather.ci evaluator cpu-sir-interp, recorded as the case hot.case
target boundary 1 of 1, the program entry: the first fault, reproduced by replay
bracket the initial state; then boundary 1
fault[E_OVERFLOW]: the exact result is outside the type's range
...
the last 20 counted operations of boundary 1, of 357848 trace events (:trace shows them all)
ord position operation operands value
...
344862 add.wrap.i64 1360, 1 1361
344863 weather.ci:25:20 index.checked.i32 1361
344864 weather.ci:25:28 index.checked.i32 1361
344865 weather.ci:25:24 mul.checked.i32 1108, 1108 1227664
344866 weather.ci:25:15 add.checked.i32 2145483528, 1227664 2146711192
344867 add.wrap.i64 1361, 1 1362
344868 weather.ci:25:20 index.checked.i32 1362
344869 weather.ci:25:28 index.checked.i32 1362
344870 weather.ci:25:24 mul.checked.i32 1096, 1096 1201216
344871 weather.ci:25:15 add.checked.i32 2146711192, 1201216 E_OVERFLOW
The lines with no position are the for loop moving i to the next index. The loop stops at its bound long before i could leave I64, so that step is recorded as a wrapping addition that cannot fault.
The index is 1362, so the reading that broke the sum was minute 1362 of day 9, at 10:42 PM: 10.96 degrees. There is nothing odd about it. The squares of day 9's readings average about 1.55 million, and 1,440 of them add up to more than an I32 holds. The fault is where the total crossed the limit, not where the data was unusual. Keep hot.case for exercise 3 of extend it.
step 4: three fixes
fix 1: a wider total
Make the total an I64, and square each reading as an I64:
I64 sum_of_squares[n](in I32[n] xs) {
I64 total = 0;
for i in 0..n {
I64 x = xs[i] as I64;
total += x * x;
}
return total;
}
In summarize, the variance becomes an I64 too:
I64 variance = sum_of_squares(day) / 1_440 - (mean as I64) * (mean as I64);
I32 spread = isqrt(variance) as I32;
$ cint run weather.ci > after.txt
$ diff golden.txt after.txt
8a9,30
> day 9: low 8.18, high 15.65, mean 12.32, spread 1.88
> day 10: low 8.77, high 16.30, mean 12.92, spread 1.87
> day 11: low 9.37, high 16.88, mean 13.51, spread 1.94
...
> day 29: low 20.21, high 27.63, mean 24.31, spread 2.00
> day 30: low 20.81, high 28.23, mean 24.92, spread 1.88
The first eight days are unchanged and the month is complete. The fault is gone.
fix 2: subtract the mean first
Put the I32 version back. This time, square each reading's distance from the mean instead of the reading itself. The distances are a few hundred at most, so their squares are small:
I32 sum_of_squared_deviations[n](in I32[n] xs, I32 mean) {
I32 total = 0;
for i in 0..n {
I32 dev = xs[i] - mean;
total += dev * dev;
}
return total;
}
I32 variance = sum_of_squared_deviations(day, mean) / 1_440;
I32 spread = isqrt(variance);
$ cint run weather.ci > after.txt
$ diff golden.txt after.txt
5c5
< day 5: low 5.79, high 13.30, mean 9.91, spread 1.93
---
> day 5: low 5.79, high 13.30, mean 9.91, spread 1.87
7,8c7,30
< day 7: low 6.98, high 14.42, mean 11.12, spread 1.88
< day 8: low 7.58, high 15.09, mean 11.71, spread 1.93
---
> day 7: low 6.98, high 14.42, mean 11.12, spread 1.87
> day 8: low 7.58, high 15.09, mean 11.71, spread 1.87
> day 9: low 8.18, high 15.65, mean 12.32, spread 1.87
...
This fix changes days the overflow never touched. Days 5, 7 and 8 now read 1.87, and so does every other day.
which spread is right
Neither cint run nor the reference can say which formula is right, because each computes exactly what its program says. So check with exact arithmetic outside cint. fractions.Fraction in Python 3.13 on Ubuntu 24.04 computes each day's variance with no rounding at all. Its square root, rounded down to hundredths as isqrt rounds, is 1.87 on all 30 days.
So fix 2 is right on every day. Fix 1 is wrong on 20 of the 30, and the first program was already wrong on days 5, 7 and 8. The cause is the formula. mean is rounded down to a whole hundredth, and the formula squares it: an error of less than 1 in mean becomes an error of up to about 2 × mean in mean * mean. As the days warm, the error grows. Subtracting the mean first keeps every number small, so the sum stays inside I32. It also changes what the rounding costs. With the distances from the rounded mean, the rounding adds only its own square to the variance, and that square is less than 1.
The golden was wrong from the start, and that went unnoticed because the spreads were never checked. Now that fix 2 is checked, save a new golden from it as a separate change.
fix 3: report instead of stopping
Put the first version back once more. This fix keeps the I32 total, but turns the overflow into an error that the program handles. add_result returns the sum, or the error overflow when the sum does not fit, and try passes that error up to the caller:
ArithError!I32 sum_of_squares[n](in I32[n] xs) {
I32 total = 0;
for i in 0..n {
total = try add_result(total, xs[i] * xs[i]);
}
return total;
}
I32 squares = sum_of_squares(day) catch (err) {
"day {d:>2}: too large to summarize in I32\n";
return;
};
I32 variance = squares / 1_440 - mean * mean;
$ cint run weather.ci
...
day 8: low 7.58, high 15.09, mean 11.71, spread 1.93
day 9: too large to summarize in I32
day 10: too large to summarize in I32
...
day 30: too large to summarize in I32
The program finishes and exits with status 0, but it answers nothing after day 8, and days 5, 7 and 8 are still wrong. Turning a fault into an error is the right fix when some inputs are truly out of range. Here the readings are ordinary and only the total is too narrow, so the error hides the problem.
what each fix changes
The reference's record of each version shows what it changed:
| Outcome | Output | Fuel | Spreads right | |
|---|---|---|---|---|
| The first program | fault on day 9 | 8 days | 38831 | 5 of 8 |
| Fix 1, a wider total | value | 30 days | 129691 | 10 of 30 |
| Fix 2, the mean first | value | 30 days | 129691 | 30 of 30 |
| Fix 3, an error | value | 8 days and 22 refusals | 114436 | 5 of 8 |
Fixes 1 and 2 have the same fuel, because they make the same calls and the same passes through their loops. Fuel follows the path a run takes, not the arithmetic on it. The outputs differ, and only the exact check showed which was right.
walk-through
I32 reading(I64 d, I64 m) computes in I64 and converts once at the end with as I32. If a reading ever left the range of I32, that conversion would fault there.
from_peak * 600 / 720 multiplies before it divides. Dividing first would make 600 / 720 zero, and the swing would disappear: every minute would read as if it were 2 PM.
isqrt(variance) is the integer square root, rounded down. It takes an integer and returns one of the same type.
ArithError!I32 is the type of a value that is either an I32 or an ArithError. A result form is a built-in such as add_result, sub_result or mul_result that returns its answer or an ArithError where the plain operator would fault.
try add_result(...) returns the error from sum_of_squares at once, when there is one, and otherwise gives the sum.
catch (err) { ... return; } runs its block when sum_of_squares returns an error. The block prints a line and leaves summarize early, so the day gets no summary and the month goes on.
extend it
- Store the readings as
I16, as many sensors send them, and change the types to match. Which fixes need a wider type for the squares, and why? - Change
readingso that each day swings twice as far. Does fix 2 still fit inI32? Work out the largest distance from the mean before you run it. - Copy
hot.caseto a folder withoutweather.ciand runcint debug locate hot.casethere. Does it reproduce the fault, and do its last operations match step 3?
reference
fault record, conversions, isqrt, result forms, error sets, catch, golden
Back to 401: labs.