find_big_2_to_nth()

This function seeks the smallest value \(2^{n}\) such that \( | ( ( 2^{n} + 1 ) - 2^{n} ) - 1 | \geq 1 \). For small values of \(n\), the expression sums to zero. For very large values of \(n\), the partial sum \( 2^{n} + 1 \) will have to round. Both outcomes will satisfy the inequality, as we'll now see.

The binary case is easy to visualize. Intuitively, the target is the smallest power of \(2\) for which \(+ 1\) falls off the right hand side. Usually, the \(1\) will just round off, but some arithmetics might round it up to the next bit position, in which case the rounded sum is \( 2^{n} + 2 \). In the diagram, the binary point is aligned to put the 1's place to the right of the digit block.

Octal and hexadecimal arithmetic behave very much the same way. Here are the values the step before \( 2^{n} + 1 \) must be rounded. Italic values are octal. Bold italic values are hex.

Our technique works in decimal, or radix 36 or 100, too. As in the octal and hex cases, repeated doubling produces a 1 digit in any radix the leading position, when there's a carry into a new place. Here is what happens with 5 significant decimal digits.

You may notice that while the mathematical description of the calculation involves a comparison against \(1\), the implementation below compares against \(0\). Historically, comparison against zero was less likely to be anomalous, hence a preference for such comparisons throughout Paranoia.

# =============================================
# Computations of fundamental system constants like radix and precisioon.
# =============================================
def find_big_2_to_nth():
    """Compute 2**n satisfying |((2**n + 1)-2**n)-1| >= 1."""
    x = ONE
    while True:
        x = x + x
        y = x + ONE
        z = y - x
        y = z - ONE
        if MINUS_ONE + fabs(y) >= ZERO: break
    # ... now x is just big enough that |((x+1)-x)-1| >= 1 ...
    return x

A more subtle issue that can arise in octal or hexadecimal arithmetic is fractional precision, which we'll see again. For example, a hex system with 26 bits available for precision would have what we call 4.5 significant hex digits, where the low-order half-digit may be thought of as a full hex digit taking just the values 0, 4, 8, or C. That is, the low-order two bits are always zero. The analysis above applies here, too.