The previous post looked at a cellular automaton introduced by Edward Fredkin. It has only two states: a cell is on or off. At each step, each cell is set to the sum of the states of the neighboring cells mod 2. So a cell is on if it had …

The previous post showed that the bits of prime powers look kinda chaotic. When you plot them, they form a triangular shape because the size of the numbers is growing. The numbers are growing geometrically, so their binary representations are growing linearly. Here’s the plot for powers of 5: You …

April 29, 2021, 2:04 p.m.

The grep utility searches text files for regular expressions, but it can search for ordinary strings since these strings are a special case of regular expressions. However, if your regular expressions are in fact simply text strings, fgrep may be much faster than grep. Or so I’ve heard. I did …

April 26, 2021, 5:31 p.m.

Suppose you need to compare two files with very long lines. Maybe each file is one line. The diff utility will show you which lines differ. But if the files are each one line, this tells you almost nothing. It confirms that there is a difference, but it doesn’t show …

April 22, 2021, 1:49 p.m.

The regular expression search utility grep has a recursive switch -R, but it may not work like you’d expect. Suppose want to find the names of all .org files in your current directory and below that contain the text “cheese.” You have four files, two in the working directory and …

March 29, 2021, 10:42 p.m.

In The Perl Cookbook, Tom Christiansen gives his rewrite of the Unix utility grep that he calls tcgrep. Why not grep with PCRE? You can get basically the same functionality as tcgrep by using grep with its PCRE option -P. Since tcgrep searches directories recursively, a more direct comparison would …

I recently received two large data files from a client, with names like foo.xlsx and foo.csv. Presumably these are redundant; the latter is probably an export of the former. I did a spot check and that seems to be the case. Then I had a bright idea: use pandas to …

The goal this post is to show how to call Perl and Python one-liners from a shell. We want to be able to use bash on Linux, and cmd or PowerShell on Windows, ideally with the same code in all three shells. Bash Bash interprets text inside double quotes but …

You can uniquely represent a large number by its remainders when divided by smaller numbers, provided the smaller numbers have no factors in common, and carry out arithmetic in this representation. Such a representation is called a Residue Number System (RNS). In the 1960’s people realized RNSs could be useful …

In the previous post we looked at how to minimize Boolean expressions using a Python module qm. In this post we’d like to look at how much the minimization process shortens expressions. Witn n Boolean variables, you can create 2^n terms that are a product of distinct variables. You can …

This post will look at how to take an expression for a Boolean function and look for a simpler expression that corresponds to the same function. We’ll show how to use a Python implementation of the Quine-McCluskey algorithm. Notation We will write AND like multiplication, OR like addition, and use …

Nov. 19, 2020, 12:32 p.m.

I’ve been thinking about Edsger Dijkstra lately because I suspect some of the ideas he developed will be useful for a project I’m working on. While searching for some of Dijkstra’s writings I ran across the article Edsger Dijkstra: The Man Who Carried Computer Science on His Shoulders. It occurred …

Most people have heard of word problems, but not as many have heard of the word problem. If you’re imagining that the word problem is some superlatively awful word problem, I can assure you it’s not. It’s both simpler and weirder than that. The word problem is essentially about whether …

Oct. 20, 2020, 12:19 a.m.

I often work in a sort of amphibious environment, using Unix software on Windows. As you can well imagine, this causes headaches. But I’ve found such headaches are generally more manageable than the headaches from alternatives I’ve tried. On the Windows command line, you can type the name of a …

The previous post looked at Gray code, a way of encoding digits so that the encodings of consecutive integers differ in only bit. This post will look at how to compute the inverse of Gray code. The Gray code of a non-negative integer n is given by def gray(n): return …

Sept. 8, 2020, 11:08 p.m.

Suppose you want to list the numbers from 0 to N in such a way that only one bit at a time changes between consecutive numbers. It’s not clear that this is even possible, but in fact it’s easy using Gray code, a method named after Frank Gray. To convert …

Sept. 8, 2020, 12:56 p.m.

I’ve been doing a little introspection lately about what software I use, not at an application level but at a feature level. LaTeX It started with looking at what parts of LaTeX I use. I wrote about this in April, and I revisited it this week in response to some …

This morning I found out that Emacs org-mode has its own markdown entities, analogous to HTML entities or LaTeX commands. Often they’re identical to LaTeX commands. For example, \approx is the approximation symbol ≈, exactly as in LaTeX. So what’s the advantage of org-entities? In fact, how does Emacs even …