AP Computer Science Principles · Unit 2 lecture · Part 4 of 11 · 8 min

2.1 Overflow and round-offWhen fixed bits run out

Mr. Thompkins
People say computers never make math mistakes. That's not quite true. Computers make two very specific kinds of mistakes, and both come from the same cause: a fixed number of bits.

In many programming languages, integers are stored using a fixed number of bits, for example 8, 16, 32 or 64. That limits the range of values: an 8-bit whole number can't go past 255, no matter what. When a calculation produces a value outside the range, the result is an overflow error. Depending on the language, the program might stop, or the extra bit might be lost so the value "wraps around" to a small number, like a car's trip odometer rolling from 999 back to 000.

25511111111+ 11100000000no room8 bits keep 00000000: it shows 0the real answer, 256, needs 9 bits
Overflow in 8 bits. 11111111 (255) plus 1 needs a ninth bit. With nowhere to put it, the stored value wraps to 0.
?Wait, what was an overflow error in Unit 1?
In Unit 1 it was one of the four error types: an error that happens when a computer attempts to handle a number outside the defined range of values. Now you can see the cause: a fixed number of bits sets that range.

Some languages hide this limit. They provide an abstraction in which the size of an integer is limited only by the computer's memory, so a number just grows as big as it needs to. The language on the AP Exam Reference Sheet is one of these: in exam pseudocode, integers don't overflow. So an exam question about overflow will always describe a fixed number of bits.

Round-off errors

Real numbers, the ones with decimal parts, have a different problem. Many of them can't be stored exactly. One third is 0.333... forever, and a computer has only a fixed number of bits for it, so it keeps an approximation. Even 0.1 has no exact binary form, the same way 1/3 has no exact decimal form. The tiny leftover is a round-off error.

You ask forMany languages store or showWhy
1 / 30.3333333333333333The 3s never end; storage does
0.1 + 0.20.300000000000000040.1 has no exact binary form
0.1 + 0.2 = 0.3falseTwo tiny round-off errors
2 / 30.6666666666666666Cut off after about 16 digits
Round-off errors in a typical language. The answers are extremely close, but not exact.
?Wait, why can't 0.1 be exact in binary?
In decimal, fractions are built from tenths, hundredths, and so on, so 1/3 never comes out even. In binary they are built from halves, quarters, eighths. One tenth isn't a sum of a finite number of those, so its binary form repeats forever and has to be cut off.

Round-off errors are usually tiny, but they matter in two places. First, comparisons: a program that checks whether 0.1 + 0.2 equals 0.3 may get false. Second, repetition: an error of one part in a quadrillion, repeated a billion times in a long simulation, can grow into something you notice. The course's takeaway: the fixed number of bits used to represent real numbers limits their range and precision, and that can cause round-off and other errors.

Pause and think
A bank stores money as a number of whole cents instead of as dollars with decimal parts. Why might that be a smart choice?
I thought about it. Show me
Whole numbers of cents are integers, which can be stored exactly (as long as there are enough bits). Dollars like 0.10 would be real numbers, which can pick up round-off errors that add up over millions of transactions.
Will it overflow?
A step counter stores today's step count as an 8-bit unsigned whole number (0 to 255), and when a value overflows the extra bit is dropped. A buggy update adds steps in chunks. (a) The count is 200 and 100 steps are added. What value is stored? (b) Which of these additions are safe: 128 + 127, 200 + 56, 15 + 240?
  1. (a) The true sum is 300. The largest 8-bit value is 255, so it overflows.
    Why?
    2⁸ = 256 patterns, 0 to 255.
  2. Dropping the extra bit is the same as subtracting 256 (the value of the lost ninth bit): 300 - 256 = 44. The counter shows 44.
    Why?
    The lost bit is the 256s place. Wrap-around arithmetic like this is how many systems behave; the AP exam only expects you to recognize that an overflow happens.
  3. (b) 128 + 127 = 255: fits. 200 + 56 = 256: overflows by 1. 15 + 240 = 255: fits.

Answer: (a) It stores 44 (300 overflows; 300 - 256 = 44). (b) 128 + 127 and 15 + 240 are safe; 200 + 56 overflows.

Stuck? Get a hint
  1. What is the biggest value 8 bits can hold?
  2. Compute each sum and compare it with 255.
  3. For the wrapped value, remove the 256s place: subtract 256.
Check yourself
A program stores whole numbers in 4 bits (0 to 15). Which calculation causes an overflow error?
  1. A6 + 9
  2. B15 - 15
  3. C7 × 2
  4. D12 + 4
Show the answer

D. 12 + 4 = 16, which is outside 0 to 15. The others give 15, 0 and 14, which all fit. 6 + 9 = 15 is the closest call, but 15 is the largest value 4 bits can hold, so it fits.

Check yourself
Which best explains why a program might display 0.30000000000000004 for 0.1 + 0.2?
  1. AThe program has a syntax error.
  2. BReal numbers are stored with a fixed number of bits, so some can only be approximated, causing round-off error.
  3. CThe sum is too big for the computer, causing overflow.
  4. DDecimal numbers cannot be stored in binary at all.
Show the answer

B. Neither 0.1 nor 0.2 has an exact binary form, so each is stored as a close approximation, and the tiny errors show up in the sum. It's a round-off error, not overflow: the number is small, not too big.

  • Fixed-size integers have a limited range. A result outside it is an overflow error.
  • Some languages, including the exam's pseudocode, limit integers only by memory, so they don't overflow.
  • Real numbers are stored with a fixed number of bits, so many are approximations: round-off errors.
  • Overflow is about too big. Round-off is about not exact.