The previous post mentioned adding a parity bit to a string of bits as a way of detecting errors. The parity of a binary word is 1 if the word contains an odd number of 1s and 0 if it contains an even number of ones. Codes like the Hamming …

Feb. 24, 2020, 10:47 p.m.

Sometimes you need to count the number of 1’s in a stream of bits. The most direct application would be summarizing yes/no data packed into bits. It’s also useful in writing efficient, low-level bit twiddling code. But there are less direct applications as well. For example, three weeks ago this …

If you know one numerical method for solving ordinary differential equations, it’s probably Euler’s method. If you know two methods, the second is probably 4th order Runge-Kutta. It’s standard in classes on differential equations or numerical analysis to present Euler’s method as conceptually simple but inefficient introduction, then to present …

In recent posts I’ve written about using RNG test suites on the output of the μRNG entropy extractor. This is probably the last post in the series. I’ve looked at NIST STS, PractRand, and DIEHARDER before. In this post I’ll be looking at TestU01. TestU01 includes three batteries of tests: …

Around this time last year I wrote about the entropy extractor used in μRNG. It takes three biased random bit streams and returns an unbiased bit stream, provided each stream as has least 1/3 of a bit of min-entropy. I’ve had in the back of my mind that I should …

There is no precise definition of what it means for a differential equation to be stiff, but essentially it means that implicit methods will work much better than explicit methods. The first use of the term [1] defined stiff equations as equations where certain implicit methods, in particular BDF, perform …

The previous post looked at computing recurrence relations. That post ends with a warning that recursive evaluations may nor may not be numerically stable. This post will give examples that illustrate stability and instability. There are two kinds of Bessel functions, denoted J and Y. These are called Bessel functions …

Fermat’s little theorem says that if p is a prime number, then for any integer b, bp-1 = 1 (mod p). This gives a necessary but not sufficient test for a number to be prime. A number that satisfies the equation above but is not prime is called a pseudoprime …

It’s easy to manipulate CSV files with basic command line tools until you need to do a join. When your data is spread over two different files, like two tables in a normalized database, joining the files is more difficult unless the two files have the same keys in the …

This post shows how to export an Excel file to a CSV file using in2csv from the csvkit package. You could always use Excel itself to export an Excel file to CSV but there are several reasons you might not want to. First and foremost, you might not have Excel. …

Sometimes you’re in the flow using the command line and you’d like to briefly switch over to Python without too much interruption. Or it could be the other way around: you’re in the Python REPL and need to issue a quick shell command. One solution would be to run your …

Top blog posts this year about command line tools. The hard part in becoming a command line wizard Computational survivalist Computing π with bc Set theory at the command line Working with wide text files Random sampling from a file

Dec. 10, 2019, 12:32 p.m.

Suppose you’re looking for instances of -42 in a file foo.txt. The command grep -42 foo.txt won’t work. Instead you’ll get a warning message like the following. Usage: grep [OPTION]... PATTERN [FILE]... Try 'grep --help' for more information. Putting single or double quotes around -42 won’t help. The problem is …

If you learned regular expressions by using a programming language like Perl or Python, you may be surprised when tools like grep seems broken. That’s because what you think of as simply regular expressions, these tools consider extended regular expressions. Tell them to search on extended regular expressions and some …

Often you have two lists, and you want to know what items belong to both lists, or which things belong to one list but not the other. The command line utility comm was written for this task. Given two files, A and B, comm returns its output in three columns: …

I’ve been reading Avi Wigdenson’s new book Mathematics and Computation. It brings a lot of interesting ideas together in compact but readable form. A couple days ago I quoted Widgerson’s comment about problems in class P often having small exponents. Here I wanted to point out another interesting comment [1]. …

The P vs NP conjecture has always seemed a little odd to me. Or rather the interpretation of the conjecture that any problem in P is tractable. How reassuring is to to know a problem can be solved in time less than some polynomial function of the size of the …

Programming languages differ in the names they use for inverse trig functions, and in some cases differ in their return values for the same inputs. Choice of range If sin(θ) = x, then θ is the inverse sine of x, right? Maybe. Depends on how you define the inverse sine. …