All the data you need.

Tag: Computing

Computing parity of a binary word
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 …
Popcount: counting 1’s in a bit stream
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 …
Runge-Kutta methods and Butcher tableau
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 …
TestU01 small crush test suite
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: …
Testing entropy extractor with NIST STS
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 …
Stiff differential equations
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 …
Stable and unstable recurrence relations
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 …
Finding large pseudoprimes
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 …
Doing a database join with CSV files
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 …
Exporting Excel files to CSV with in2csv
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. …
Minimizing context switching between shell and Python
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 command line posts of 2019
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
Why can’t grep find negative numbers?
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 …
Why doesn’t grep work?
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 …
Set theory at the command line
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: …
Quantum mechanics via quantum computing
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]. …
NP vs small P
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 …
Inverse trig function implementations
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. …