Chapter 7: The Floating-Point Trap

We did it. By transforming our domino puzzle into a bipartite graph and finding the eigenvalues of the adjacency matrix, we derived Pieter Kasteleyn’s masterpiece.

To find the exact number of perfect tilings for any $M \times N$ board, all we need is this beautiful, universal closed-form equation:

(Note: If you plug an odd-by-odd board into this formula, like $3 \times 3$, one of the cosines evaluates to exactly $\cos(\pi/2) = 0$, perfectly collapsing the entire product to zero!)

Let’s finally answer the question that broke our computer science algorithms. What happens if we plug in a standard $64 \times 64$ checkerboard ($M=64$, $N=64$)?

The formula spits out an integer with over 500 decimal digits. It is roughly $2.53 \times 10^{511}$. To put that into perspective, the estimated number of atoms in the observable universe is only $10^{80}$. The number of ways to arrange wooden blocks on a $64 \times 64$ grid vastly outnumbers the physical particles in existence.

But there is a massive, hilarious catch hiding in this beautiful equation.

The Floating-Point Trap

As a programmer, your first instinct is probably to boot up Python or C and write a simple nested for loop to calculate this product. It seems ridiculously easy.

In Python, your code would look something like this:

import math

def kasteleyn_tilings(M, N):
    total = 1.0
    for j in range(1, math.ceil(M / 2) + 1):
        for k in range(1, math.ceil(N / 2) + 1):
            term1 = 4.0 * math.cos(math.pi * j / (M + 1))**2
            term2 = 4.0 * math.cos(math.pi * k / (N + 1))**2
            total *= (term1 + term2)
    return total

print(kasteleyn_tilings(8, 8)) 

If you run this script for an $8 \times 8$ board, it outputs 12988816.000000004.

Wait a minute. You can’t have 0.000000004 of a domino layout. The exact, pure mathematical answer for an $8 \times 8$ board is exactly 12,988,816. Why did Python attach garbage decimals to the end?

Because of floating-point arithmetic.

Computers cannot store irrational numbers like $\pi$ or the exact output of a cosine wave perfectly. They store approximations using the IEEE 754 double-precision standard. A 64-bit float can only hold about 15 to 17 significant decimal digits before it runs out of physical memory to store the precision.

Every time your script calculates math.cos() or uses math.pi, it introduces a tiny, microscopic rounding error. When you multiply those errors together inside a nested loop, the error compounds.

For an $8 \times 8$ board, it’s just an annoying decimal. But what if you run this script for a $16 \times 16$ board? The exact answer is a 36-digit integer. But your floating-point variable only holds 15 digits of precision.

The computer will correctly calculate the first 15 digits, and then the bottom 21 digits will be literal, unadulterated garbage. The precision loss entirely destroys the answer. We have a formula that calculates the exact integer, but our hardware is physically incapable of executing it without corrupting the math.

The Thermodynamic Limit

Before we solve the floating-point crisis, we need to address why a physicist was solving this problem in the first place, and why they didn’t care about the precision limit.

Physicists don’t care about $8 \times 8$ checkerboards. They care about statistical mechanics and what happens when the board approaches infinity. In physics, this is called the thermodynamic limit.

If the board is infinitely large, how fast does the entropy—the number of possible tilings—grow? By transforming the discrete sums of Kasteleyn’s formula into a continuous double integral, mathematicians were able to calculate the asymptotic growth rate. As the board scales to infinity, the number of ways to tile it grows by exactly this factor per square:

Here, $G$ is Catalan’s constant (roughly 0.9159). Deep within the chaos of an infinitely massive grid of dominoes, the entropy perfectly aligns with one of the most mysterious constants in mathematics.

To a physicist, this is the final answer. If you ask them how many tilings exist on a $64 \times 64$ board, they will happily approximate it as $1.3385^{4096}$, pack up their chalkboard, and go home.

The Computer Scientist’s Obsession

But we are not physicists. We are computer scientists, and we have a very different motivation.

Combinatorics is the mathematics of the absolute. The original Russian Olympiad judges from 1994 didn’t ask for an approximation or an asymptotic growth rate. They asked for the exact number of ways to tile the grid. A floating-point approximation that corrupts the bottom 200 digits of our answer is unacceptable. It is a failure of computation.

We want the exact, pristine, uncorrupted integer. We want to push the physical limits of our CPU and RAM to conquer a massive, discrete grid. We want all 500 digits of the $64 \times 64$ board simply because we know they exist, and hardware limitations shouldn’t dictate mathematical truth.

The Path Forward

The physics are beautiful, but we are engineers. We have a massive board to calculate, and our floating-point CPU just spat out garbage.

To calculate a 500-digit integer accurately, we cannot use decimals. We cannot use approximations of $\pi$. We must find a way to compute a massive trigonometric equation using absolutely nothing but pure, exact integers.

To do that, we have to banish the cosine wave entirely and step into the world of abstract algebra and cyclotomic polynomials.