All the data you need.

Tag: Computing

How probable is a probable prime?
A probable prime is a number that passes a test that all primes pass and that most composite numbers fail. Specifically, a Fermat probable prime is a number that passes Fermat’s primality test. Fermat’s test is the most commonly used, so that’s nearly always what anyone means by probable prime …
Accurately computing a 2×2 determinant
The most obvious way to compute the determinant of a 2×2 matrix can be numerically inaccurate. The biggest problem with computing ad – bc is that if ad and bc are approximately equal, the subtraction could lose a lot of precision. William Kahan developed an algorithm for addressing this problem. …
Convert PostScript to PDF locally
There are numerous web sites that will let you upload a PostScript (.ps) file and download it as a PDF. Some of these online file format conversion sites look sketchy, and the ones that seem more reputable don’t always do a good job. If you want to convert PostScript to …
On using your computer as more than a terminal
Here are five things I appreciate about using Emacs. They also apply to any software that runs entirely on your computer. It doesn’t track me. It doesn’t show me ads. It doesn’t require two-factor authentication. It doesn’t change unless I change it. It doesn’t stop working if my internet connection …
LaTeX command frequencies
In the previous post I present a bash one-liner to search directories for LaTeX files and count the commands used. College files I first tried this out on a directory that included some old files from grad school. I chose this directory because I knew it had a lot of …
A shell one-liner to search directories
I started this post by wanting to look at the frequency of LaTeX commands, but then thought that some people mind find the code to find the frequencies more interesting than the frequencies themselves. So I’m splitting this into two posts. This post will look at the shell one-liner to …
Making an invertible function out of non-invertible parts
How can you make an invertible function out of non-invertable parts? Why would you want to? Encryption functions must be invertible. If the intended recipient can’t decrypt the message then the encryption method is useless. Of course you want an encryption function to be really hard to invert without the …
Three composition theorems for differential privacy
This is a brief post, bringing together three composition theorems for differential privacy. The composition of an ε1-differentially private algorithm and an ε2-differentially private algorithm is an (ε1+ε2)-differentially private algorithm. The composition of an (ε1, δ1)-differentially private algorithm and an (ε2, δ2)-differentially private algorithm is an (ε1+ε2, δ1+δ2)-differentially private algorithm. …
How to Set Num Lock on permanently
When I use my Windows laptop, I’m always accidentally brushing against the Num Lock key. I suppose it’s because the keys are so flat; I never have this problem on a desktop. I thought there must be some way to set it so that it’s always on, so I searched …
Extended floating point precision in R and C
The GNU MPFR library is a C library for extended precision floating point calculations. The name stands for Multiple Precision Floating-point Reliable. The library has an R wrapper Rmpfr that is more convenient for interactive use. There are also wrappers for other languages. It takes a long time to install …
When is round-trip floating point radix conversion exact?
Suppose you store a floating point number in memory, print it out in human-readable base 10, and read it back in. When can the original number be recovered exactly? D. W. Matula answered this question more generally in 1968 [1]. Suppose we start with base β with p places of …
MDS codes
A maximum distance separable code, or MDS code, is a way of encoding data so that the distance between code words is as large as possible for a given data capacity. This post will explain what that means and give examples of MDS codes. Notation A linear block code takes …
Computing the area of a thin triangle
Heron’s formula computes the area of a triangle given the length of each side. where If you have a very thin triangle, one where two of the sides approximately equal s and the third side is much shorter, a direct implementation Heron’s formula may not be accurate. The cardinal rule …
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 …