2.1 Exhaustive Testing & the Calculator

Theory: Exhaustive Testing & the Calculator

Principle 2 in 1.5 says that exhaustive testing is impossible. It is easy to nod at that sentence and much harder to feel it. So in class the professor did not argue it; the class tried it. Each group had to plan a brute force test of a simple calculator and then estimate how many tests it would need. The numbers that came out are the best argument for everything else in this lecture.

Brute Force: Try Everything

Your phone has a 4-digit PIN. There are 10,000 possible PINs, from 0000 to 9999. A thief who simply types all 10,000 of them, one after another, is using brute force: no cleverness, no skipping, every possibility in turn.

Brute force testing applies the same idea to software: run the program with every possible input and check every answer. Testing everything with nothing skipped is called exhaustive testing. If we could do it, we would know for certain that the program has no bugs for any input.

Writing a Test Plan

Before trying everything, you still need a plan. A plan starts with test objectives. A test objective is the goal of a group of tests. For a calculator, the obvious objectives are: test addition, test subtraction, test multiplication, test division.

Under each objective you write test cases. Recall from Lecture 1 that a test case has two parts: the input (for example 1 + 0) and the expected result (here 1), decided before the test is run. Running the test means comparing the calculator’s actual answer with that expected result.

Many companies write the plan as a table with three columns: the objective, the test cases and remarks. The exact format differs from company to company; the content is what matters.

Test objective	Test cases (input → expected result)	Remarks
1. Test addition	1 + 0 → 1, 1 + 1 → 2, … up to 32-digit numbers	Positive tests. Brute force means trying all of them.
2. Test addition with negative and decimal numbers	-5 + 3 → −2, 1.0 + 0.1 → 1.1	Same idea, many more combinations.
3. Test wrong input	1 + a, 1A1 + 2	Negative tests. The expected result is what the specification says should happen.
4. Test the Clear key and the +/− key	Press Clear in the middle of a sum; change the sign, then add	Each extra key multiplies the number of tests again.

Positive and negative tests

Look at row 3. Nobody should type 1 + a, but real users press the wrong key all the time, so the calculator must handle it. This gives two kinds of test:

• A positive test uses input that is allowed, such as 5 + 3.
• A negative test uses input we do not expect but that is still possible, such as 5 + a. Its expected result is whatever the specification says should happen (an error message, say).

When the professor talked about testing “all combinations”, he meant positive and negative tests together.

Counting the Tests

Go back to the PIN. One digit has 10 choices. Two digits have $10 \times 10 = 100$. Four digits have $10^4 = 10{,}000$. Every new digit multiplies the number of choices by 10.

Digits	1	2	4 (a PIN)	6	32
Choices	10	100	10,000	1,000,000	$10^{32}$

The class calculator accepts numbers of up to 32 digits, so:

• One number has $10^{32}$ possible values (a 1 followed by 32 zeros).
• A sum needs two numbers, and every first number can be paired with every second number, so we multiply:

$$10^{32} \times 10^{32} = 10^{64}$$

• Signs. A number can be positive or negative, which doubles its choices. Letting just one of the two numbers carry a sign gives $2 \times 10^{64}$; letting both carry one gives $4 \times 10^{64}$. Either way the size is about $10^{64}$, and the class worked with the smaller figure:

$$\text{tests for addition alone} \approx 2 \times 10^{64}$$

And that is only whole-number addition. Decimals, wrong input, the Clear and +/− keys, and the other three operators all multiply the count again.

Some groups in class wrote down 400 test cases. The professor’s verdict: that is not exhaustive testing. Exhaustive means everything, and any number far smaller than the real input space, however large it looks on paper, is a sample, not exhaustive.

How Long Would It Take?

Now turn the count into time. Suppose a person presses one key per second. A typical number has about 16 digits, so typing one number takes about 16 seconds, and a test with two numbers takes about 30 seconds, half a minute.

$$2 \times 10^{64} \text{ tests} \times 0.5 \text{ min} = 10^{64} \text{ minutes}$$

A year has $365 \times 24 \times 60 = 525{,}600$ minutes, roughly $5.3 \times 10^{5}$:

$$\frac{10^{64}}{5.256 \times 10^{5}} \approx 1.9 \times 10^{58} \approx 2 \times 10^{58} \text{ years}$$

What if a computer types for us?

The professor then asked the obvious follow-up: let a program enter the numbers. Suppose each test takes 1 microsecond (one millionth of a second), a million times faster than the person.

$$2 \times 10^{64} \times 10^{-6} \text{ s} = 2 \times 10^{58} \text{ s}, \qquad \frac{2 \times 10^{58}}{3.16 \times 10^{7} \text{ s/year}} \approx 6 \times 10^{50} \text{ years}$$

A million times faster only removes six zeros out of fifty-eight. For comparison, the universe is about $1.4 \times 10^{10}$ years old.

A faster machine does not solve the problem; the number of tests is simply too big. Automation changes the time per test, never the number of combinations.

Exam radar: Exhaustive (brute force) testing means testing all combinations of input and output. Even a very simple calculator needs about $10^{64}$ tests for addition alone, so exhaustive testing is impossible. Because of this, testing is a risk-based activity: we must choose what to test, and some risk always remains. (How to choose is the subject of 2.2.)

Doing the Count in an Exam

A counting question in the exam usually uses a smaller, cleaner input space. The procedure:

1. Write down every independent choice: operands, signs, operators, formats, sequences, and any invalid-input categories the question asks for.
2. Count the possible values in each choice.
3. Multiply the sizes of independent choices. Add only separate categories that never combine with each other.
4. Multiply the number of tests by the time for one test.
5. Convert the time carefully: seconds → minutes → hours → days → years.
6. Conclude whether exhaustive testing is practical, remembering that automation changes the time per test, not the number of combinations.

Common mistake: adding the sizes of choices that combine. If every value of the first input can be paired with every value of the second, there are $1000 \times 1000$ pairs, not $1000 + 1000$. Add only when the categories never occur together in one test.

---

Worked Examples

Exercise 1

A calculator takes two numbers. Each number has up to 32 digits and can be positive or negative. About how many test cases does exhaustive testing of one addition need? About how long does it take at 30 seconds per test?

Show solution ↓Hide solution ↑

Solution

Count. One 32-digit number has $10^{32}$ possible values. A sum pairs every first number with every second number, so we multiply:

$$10^{32} \times 10^{32} = 10^{64}$$

The sign at least doubles this (×2 for one signed number, ×4 if both are signed), so the count is about $2 \times 10^{64}$ test cases (of order $10^{64}$).

Time. 30 seconds is half a minute:

$$2 \times 10^{64} \times 0.5 \text{ min} = 10^{64} \text{ min}$$

One year has $525{,}600 \approx 5.3 \times 10^5$ minutes:

$$\frac{10^{64}}{5.3 \times 10^{5}} \approx 2 \times 10^{58} \text{ years}$$

About $2 \times 10^{58}$ years, which is unimaginably longer than the age of the universe ($\approx 1.4 \times 10^{10}$ years). Exhaustive testing is impossible.

Exercise 2

A computer types the numbers one million times faster than a person (1 microsecond per test). Does this make exhaustive testing of the calculator possible?

Show solution ↓Hide solution ↑

Solution

No. The number of tests does not change; only the time per test does.

$$2 \times 10^{64} \times 10^{-6} \text{ s} = 2 \times 10^{58} \text{ s}$$

A year is about $3.16 \times 10^7$ seconds, so this is about

$$\frac{2 \times 10^{58}}{3.16 \times 10^{7}} \approx 6 \times 10^{50} \text{ years}$$

Being a million times faster removes only six zeros. The time is still about $6 \times 10^{50}$ years, so speed cannot fix the problem: the number of tests is too big, and we must choose which tests to run by risk.

Exercise 3

A calculator accepts two integers from 000 through 999 and supports four operators. An automated test takes 0.02 seconds. How many exhaustive input combinations exist, and how long would one complete run take?

Show solution ↓Hide solution ↑

Solution

Step 1: count each independent choice.

• First operand: 000 to 999 gives 1,000 values.
• Second operand: 1,000 values.
• Operator: 4 values.

Step 2: multiply (every operand can be paired with every other operand and every operator):

$$1000 \times 1000 \times 4 = 4{,}000{,}000 \text{ tests}$$

Step 3: total time.

$$4{,}000{,}000 \times 0.02 \text{ s} = 80{,}000 \text{ s}$$

Step 4: convert the units. $80{,}000 \div 60 = 1{,}333$ minutes remainder 20 seconds. $1{,}333 \div 60 = 22$ hours remainder 13 minutes. So

$$80{,}000 \text{ s} = 22 \text{ h } 13 \text{ min } 20 \text{ s}$$

Check: $22 \times 3600 + 13 \times 60 + 20 = 79{,}200 + 780 + 20 = 80{,}000$ ✓

Conclusion: the restricted input space has 4,000,000 tests, and one run takes about 22 hours 13 minutes 20 seconds. That is already expensive, and adding signs, decimals, invalid inputs or key sequences would multiply the count further.

Exercise 4

For the calculator in Exercise 3, a student writes: ”$1000 + 1000 + 4 = 2{,}004$ tests, which takes about 40 seconds.” What is wrong with this answer?

Show solution ↓Hide solution ↑

Solution

The student added the sizes of choices that combine. In one test the calculator receives a first operand and a second operand and an operator, and every value of each can occur together with every value of the others. The number of possible tests is therefore the number of combinations, which is a product:

$$1000 \times 1000 \times 4 = 4{,}000{,}000 \ne 2{,}004$$

Adding would be right only for separate categories that never occur in the same test. The correct time is $4{,}000{,}000 \times 0.02 = 80{,}000$ s, about 22 hours 13 minutes 20 seconds, not 40 seconds.

Exercise 5

Classify each test of the calculator as positive or negative, and say whether a plan containing 400 such test cases is exhaustive:

(a) 12 + 30 (b) 7 + b (c) -4 + 2.5 (d) 1A1 + 2

Show solution ↓Hide solution ↑

Solution

A positive test uses allowed input; a negative test uses unexpected but possible input, and its expected result is whatever the specification says should happen.

• (a) 12 + 30: allowed input, positive.
• (b) 7 + b: a letter where a number belongs, negative.
• (c) -4 + 2.5: negative numbers and decimals are allowed values, so this is positive (it belongs to the “negative and decimal numbers” objective, but it is still allowed input).
• (d) 1A1 + 2: invalid characters, negative.

A plan with 400 test cases is not exhaustive. Exhaustive means every possible input, and the real space is about $10^{64}$ for addition alone. Any number far smaller than that is a sample.

Exercise 6

Explain why exhaustive testing is impossible and how this changes test planning.

Show solution ↓Hide solution ↑

Solution

Exhaustive testing is impossible because the number of inputs, input sequences, internal paths, states and environment combinations grows far beyond the time and resources available. Even a simple calculator has an enormous cross-product of operand values, signs, operators, decimals and invalid inputs: about $10^{64}$ tests for addition alone, which would take about $2 \times 10^{58}$ years by hand and still about $6 \times 10^{50}$ years by machine. Loops and branches cause a similar explosion of execution paths inside the code.

Test planning must therefore accept that we test a sample and that not all failures are equally important. The team estimates how often each failure could happen and how much it would cost, tests the high-risk features first (2.2), and uses sampling techniques such as equivalence partitioning, boundary value analysis and MC/DC (Lectures 3–5) to choose a small set of tests that still finds many bugs. Testing reduces the remaining risk, but it cannot prove that no defects remain.