# 1.22 Numerical Limits

Algorithms are usually described with mathematical integers and real numbers. Implementations run with finite machine values. This difference matters. An algorithm can be correct in theory and still fail in code because an integer overflows, a floating-point comparison is unstable, or a counter cannot represent the true answer.

Numerical limits should be checked during design, not after debugging. The input constraints often tell you which numeric type is required.

## Problem

You need to choose numeric types and arithmetic operations that preserve the algorithm's intended meaning under the given constraints.

## Solution

Compute the largest and smallest possible intermediate values, not only the largest input value.

Use this checklist:

```text
1. Identify all numeric input ranges.
2. Bound all sums, products, differences, and counters.
3. Check whether intermediate values exceed the chosen type.
4. Use wider types when needed.
5. Avoid unstable floating-point equality tests.
6. Add overflow-aware tests near the limits.
```

The important word is "intermediate." A final answer may fit in a type while a temporary calculation overflows.

## Example: Array Sum

Suppose the constraints are:

```text
n <= 10^6
-10^9 <= A[i] <= 10^9
```

The largest possible absolute sum is:

```text
10^6 * 10^9 = 10^15
```

A 32-bit signed integer holds values only up to about:

```text
2.1 * 10^9
```

So a 32-bit integer is not enough. The implementation should use a 64-bit integer for the sum.

```text
sum = 0 as 64-bit integer

for x in A:
  sum = sum + x
```

## Example: Pair Products

Suppose an algorithm compares products:

```text
A[i] * A[j] < A[k] * A[l]
```

If each value can be as large as (10^9), each product can reach (10^{18}). This fits in a signed 64-bit integer only barely, since the limit is about (9.22 \cdot 10^{18}). If values may exceed that, use arbitrary precision integers or compare without multiplying when possible.

For fractions, instead of comparing:

```text
a / b < c / d
```

many integer algorithms use cross multiplication:

```text
a * d < c * b
```

This avoids floating-point division, but it can overflow. The safer method depends on the language and constraints.

## Example: Binary Search Midpoint

This midpoint formula may overflow in fixed-width integer languages:

```text
mid = (left + right) // 2
```

If `left` and `right` are both large, their sum may exceed the integer limit. Prefer:

```text
mid = left + (right - left) // 2
```

This computes the same midpoint without forming the large sum.

## Counting Outputs

Counts can grow faster than values in the input.

Example:

```text
Number of pairs in an array of length n:
n * (n - 1) / 2
```

For (n = 10^6), this is about:

```text
5 * 10^11
```

So a pair counter needs 64-bit storage even though the index itself may fit in 32 bits.

For subsets, the count is (2^n). For permutations, the count is (n!). These values exceed fixed-width integers quickly.

## Floating-Point Values

Floating-point numbers approximate real numbers. They are useful for measurement, geometry, probabilities, and optimization, but they need careful comparisons.

Avoid direct equality checks:

```text
if x == y:
```

when `x` and `y` are computed floating-point values.

Prefer tolerance-based comparisons:

```text
abs(x - y) <= eps
```

The tolerance `eps` should match the scale of the problem. A fixed tolerance such as `1e-9` may be too strict for large values and too loose for very small values.

For geometry, orientation tests such as cross products are especially sensitive. If input coordinates are integers and bounds are moderate, integer arithmetic is often more reliable than floating-point arithmetic.

## Infinity Sentinels

Many graph and dynamic programming algorithms use a large value to mean infinity.

```text
INF = very large number
```

Choose `INF` so that adding a valid cost does not overflow.

Bad pattern:

```text
INF = max_integer
dist[v] = min(dist[v], dist[u] + w)
```

If `dist[u]` is `INF`, then `dist[u] + w` may overflow.

Safer pattern:

```text
if dist[u] != INF:
  dist[v] = min(dist[v], dist[u] + w)
```

Also choose `INF` larger than any valid answer but small enough that safe additions remain representable.

## Modular Arithmetic

Some problems ask for answers modulo a number such as (10^9 + 7). In that case, the stored value is no longer the exact count. It is the remainder.

Use modular arithmetic only when the problem permits it.

For addition:

```text
(a + b) mod M
```

For multiplication:

```text
(a * b) mod M
```

Even modular multiplication can overflow before the modulus is applied if `a * b` exceeds the machine type. Use a wider type or a safe multiplication routine when needed.

## Common Pitfalls

Do not choose numeric types from input values alone. Intermediate results may be much larger.

Do not assume mathematical division and programming-language division behave the same for negative integers.

Do not compare floating-point results with exact equality unless the values are known to be exactly representable.

Do not set infinity to the maximum integer if later operations add to it.

Do not forget that array indices, counts, sums, and products may need different types.

## Takeaway

Numerical limits are part of the algorithmic contract. Bound intermediate values, choose types that can represent them, avoid overflow-prone formulas, and treat floating-point comparisons as approximate unless exact arithmetic is available.