Posted on 2023-06-30 15:31

Set operations using bit arrays

Let $X, Y \subseteq \lbrace 0, 1, \ldots, N \rbrace$. These sets can be written in equivalent form as bit arrays of size $N + 1$. Let $x$ be the bit array form of $X$ (and similarly, $y$ of $Y$): the bit $x_i$ is flipped iff $i \in X$, and not set otherwise (where $i \in \lbrace 0, \ldots, N \rbrace$). Such bit arrays enable the following set operations:

  • The membership test of $i \in X$ is given by (x >> i) & 1.
  • The complement $X^\complement$ is given by ~x.
  • The intersection $X \cap Y$ is given by x & y.
  • The union $X \cup Y$ is given by x | y.
  • The relative complement $X \setminus Y$ is given by x & ~y.
  • The symmetric difference $X~\Delta~Y$ is given by (x & ~y) | (y & ~x), which is equivalent to x ^ y.

These operations can be performed very efficiently in hardware, which sometimes offers substantial performance gains over other approaches (e.g., those based on hash sets).

Posted on 2022-09-25 11:15

Tail-call optimisation in Python using ast

Python does not have tail-call optimisation (TCO), and it likely never will. Several packages exist that add TCO via decorators (e.g., tco). Most of these packages use some lambda calculus to implement TCO. In this post I want to explore an alternative way to achieve TCO, using the ast module to rewrite the decorated function. Read more (4 min)

Posted on 2020-11-25 15:29

Population and market integration in the Roman hinterland

This post is a based on our presentation at the EAA Annual Meeting in August 2020 (slides)

The Roman Empire was a remarkable achievement in world history: extending from the north of England to the Syrian Desert and Morocco at the height of its powers it integrated a population of some 60-100 million into one political, cultural and economic unit. For a few centuries this generated a remarkable growth in population.

To understand how this could be we have to focus on rural developments, and the best data for that are obtained by the many archaeological field surveys of the last half century. Read more (19 min)

Posted on 2020-11-22 22:22

Test post

First post using Nikola. I use this post to compare how things render in various themes. Read more (1 min)