How do computers round numbers?

2026-10-05

Tags: Maths

Anyone who knows anything about maths sort of just knows how to round a number, but many can't explain how it works using basic arithmetic operators. It must be super complicated, right? So how do computers do it so fast?

Continuity

The truth is, nobody can explain rounding using a finite number of add, subtract, multiply and divide operations. It's mathematically impossible.

The reason for this is continuity. Many mathematical problems, especially those that lend themselves well to programmatic solutions, are "continuous" - that is to say, any change to an operand changes the result. For example, with multiplication, \(1.1 \times 2 = 2.2\), and \(1.11 \times 2 = 2.22\).

In a non-continuous problem, such as rounding, the result goes in steps, rather than a continuous line: \(\lceil1.1\rceil = 2\), but \(\lceil1.11\rceil = 2\) as well. It's not until we get to \(\lceil2.\dot{0}\dot{0}1\rceil\) that the result jumps up to \(3\).

So, how do we solve it?

Formal definition

The formal definition for the ceiling operation is:

\[ \lceil x \rceil = n \iff n - 1 < x \leq n,\qquad n \in \mathbb{Z} \]

Looks sort of complicated, but it's easy once you get the symbols.

Somewhat counterintuitively, we have to start at the right, where we find out about \(n\). \(\in\) means "in", and \(\mathbb{Z}\) is the set that contains all integers, so from \(n \in \mathbb{Z}\) we know that "\(n\) is in the set that contains all integers", i.e., \(n\) is a whole number.

\(\iff\) means "if and only if" - so, "the ceiling of x is equal to n if and only if x is between n and n-1".

From these two facts, we can figure out the result. We just have to test \(x\) against every possible value of \(n\), of which there are...

Oh.

A lot?

A lot.

Surely there's a way to figure out the answer in finite time.

The inefficient way

Thankfully, our computers don't know about infinitely many numbers. An IEEE 754 64-bit double can express \(2^{64}\), or \(18,446,744,073,709,551,616\) discrete values, which is a lot, but far better than infinity!

We can just start at the minimum integral value of a double, and increment it by 1 until we find the first integer that is greater than our target. Here's an example in C:

double ceiling(double x)
{
    double n = -9007199254740992.0;  // -2^53

    while (n <= x)
    {
        n += 1.0;
    }

    return n;
}

However, nobody wants an algorithm whose worst-case time complexity is \(O(2^{64})\).

Bit shifting

Lucky for us, there's a better way, using the magic of binary.

A double is, fundamentally, expressed like so:

\[ x = (-1)^s \times (1.f) \times 2^e \]

Where:

\(s\) is the sign,
\(f\) is the fractional component,
and \(e\) is the exponent.

This means that we can use bitwise logic to isolate and destroy the fractional component. Then, if the fractional component was greater than 0, we add 1 to make sure we rounded upwards.

There are a couple of optimisations we can do, here. For special values NaN (not-a-number) and positive or negative infinity, those values round to themselves and we can return them right away. We can also infer the value if \(x\) was between -1 and +1 exclusive (though we have to make sure that we preserve the difference between -0 and +0). We also know that if the exponent is 52 or greater, there's no space for a fractional component, so that's another case where we can return as-is.

Here's an implementation in C:

#include <stdint.h>
#include <string.h>

#define DOUBLE_FRACTION_BITS    52
#define DOUBLE_EXPONENT_MAX     0x7FF
#define DOUBLE_EXPONENT_BIAS    1023
#define DOUBLE_SIGN_MASK        0x8000000000000000ULL
#define DOUBLE_EXPONENT_MASK    0x7FF0000000000000ULL

double ceiling(double value)
{
    uint64_t    bits;
    int         sign;
    uint64_t    exponent_bits;
    int         exponent;
    int         fractional_bit_count;
    uint64_t    discarded_mask;
    uint64_t    rounded_bits;
    uint64_t    integer_unit;
    double      result;

    memcpy(&bits, &value, sizeof(bits));

    sign = (bits & DOUBLE_SIGN_MASK) != 0;
    exponent_bits = (bits & DOUBLE_EXPONENT_MASK) >> DOUBLE_FRACTION_BITS;
    exponent = (int)exponent_bits - DOUBLE_EXPONENT_BIAS;

    if (exponent_bits == DOUBLE_EXPONENT_MAX // value is NaN or +-infinity 
        || exponent >= DOUBLE_FRACTION_BITS) // no fraction when e>=52
    {
        return value; 
    }

    if (exponent < 0) // when -1 < x < 1, the sign tells us the value 
    {
        if ((bits & ~DOUBLE_SIGN_MASK) == 0) // preserve +0 and -0 
        {
            return value;
        }

        return sign ? -0.0 : 1.0;
    }

    fractional_bit_count = DOUBLE_FRACTION_BITS - exponent;
    discarded_mask = (1ULL << fractional_bit_count) - 1;

    if ((bits & discarded_mask) == 0) // fraction was 0; already integer 
    {
        return value;
    }

    rounded_bits = bits & ~discarded_mask;

    if (!sign)
    {
        integer_unit = 1ULL << fractional_bit_count;
        rounded_bits += integer_unit;
    }

    memcpy(&result, &rounded_bits, sizeof(result));
    return result;
}

Assembly and circuitry

Bit-shifting is fast, but rounding can be faster.

Most modern processors contain an operation specifically for rounding. In x86 assembly, it's called ROUNDSD, and it takes 3 parameters: the output register, the input register, and the rounding mode (0b00 for nearest, 0b01 for downwards, 0b10 for upwards, and 0b11 for towards 0).

The instruction causes the operation to be dispatched to a logical circuit designed specifically for rounding, so the operation completes in a single clock cycle. It doesn't get much faster than that.

This circuit is massive and immensely complicated, with 64 inputs and 64 outputs. Chip manufacturers don't tend to share their designs, so we can only speculate as to what they look like in practice, but drawing out a proof-of-concept diagram is a job for someone with a lot more patience than I.

Many compilers will dispatch rounding to this instruction on ISAs that support it, and fall back to a bit-shifting implementation for those that don't.

Adapted for floor, nearest, and towards-zero

The floor operation is very close to ceiling: the only difference is that instead of rounding up 1 for positive fractional components, we round down 1 for negative ones.

\[ \lfloor x \rfloor = n \iff n \le x < n + 1, \qquad n \in \mathbb{Z} \]

For the nearest integer, we start branching some more. We need to know about the specific value of the discarded fraction, rather than if it was 0 or not. If it was less than 0.5, keep it as-is; if it was greater than 0.5, add 1 for positive numbers and subtract 1 for negatives.

Those of you who have been wronged by an edge case may be asking, what about a fraction of exactly 0.5? Well, in that case, we have a choice to make. Many people think it's right to round away from 0, but another common practice - employed in ROUNDSD - is "banker's rounding", where we clamp away from 0 only if the number is odd. This method is thought to just about level out rounding errors over time in financial transactions.

\[ \operatorname{bankersRound}(x)=n \iff \begin{cases} n-\frac{1}{2} < x < n+\frac{1}{2}, & n \in \mathbb{Z},\\[4pt] x=n+\frac{1}{2} \;\land\; n \text{ is even},\\[4pt] x=n-\frac{1}{2} \;\land\; n \text{ is even}. \end{cases} \]

And rounding towards 0 ("truncating") is simple: just discard the fractional bits. That's it.

\[ \operatorname{trunc}(x) = n \iff \begin{cases} n \le x < n+1, & x \ge 0,\\[4pt] n-1 < x \le n, & x < 0, \end{cases} \qquad n \in \mathbb{Z} \]

Conclusion

Rounding numbers programmatically is deceptively complicated when you start thinking about it, and beautifully efficient when you start thinking with ~~portals~~ binary instead of traditional decimal algebra.

posh.wiki