XKCD 2585 Implemented: Round the world ⏹ ⏺

^{© Randall Monroe, 2022}

Pulling any number of any number by repeatedly cramming one into a bunch of units and rounding until it starts looking like the other.

Try it out at https://rounding.lam.io!

Technical Overview

This is a fairly straightforward use of the Wikipedia Convert module's database of units, which I reused from a previous project (phrase2unit: Implementing XKCD 2312). All this is doing is a greedy linear search of all units that match the input kind, which is sparse enough (<100k entries) that this isn't very expensive. In fact sparsity is a big problem with the original dataset, which doesn't fill the real line enough to converge for most pairs of numbers and units. Since units can be arbitrarily combined, the live implementation uses a cross product of all units in the base Wikipedia database (and their reciprocals), which gives decent performance and coverage at the expense of some very weird-looking but valid units.

Most of the heavy lifting is done by Postgres, specifically this linear search of all valid unit conversions post-rounding:

SELECT * FROM (
  SELECT *, ABS(LOG(st0.vto / <target quantity>)) AS diff FROM (
    SELECT long_name AS vto_unit_long,
           name AS vto_unit,
           factor,
           ROUND(<starting quantity> / factor) * factor AS vto
    FROM units
    WHERE pool = %s AND factor > 0
      AND si_m=%s AND si_s=%s AND ...
  ) st0 WHERE st0.vto > 0
) st1 ORDER BY st1.diff ASC LIMIT 1;

which is really as brute force as it looks, a sequential scan without any indexing after cutting the list to the units that match the queried unit. Looking at the number of matching units in the worst case I had alluded that it stays <100k entries, so this is pretty tractable.

Unit stats

The base units that Wikipedia provides have an interesting distribution, with energy having the most diverse offerings:

The combined units have themselves a different mix of units of course, although it is fortunate that many of the ones near the top are named, common units that people like to try:

Next steps

Further optimizations are difficult, especially within the constraints of an RDBMS. Since where the 0.5 cliffs land depends so wildly on the input, it's pretty much impossible to make any pre-built indexing structure that will serve all inputs. It is possible to progressively search for ranges (e.g. to increment, to look for numbers that will generate 0.5-1, then 1.5-2, etc.) although finding numbers that land in lower ranges won't necessarily be the fastest to advance since landing at say 0.99 has much smaller gains than landing at 20.5. If there were much larger inputs and search spaces it might be worth doing this progressive search and finding a reasonably threshold but for now with this set of units brute force is actually not bad and has minimal overhead.