Notes on math, tech, and everything in between
It is intuitive that removing even a single point from a line disconnects it, but removing a finite set of points from a plane leaves it connected. A line disconnected by a single point. A plane remaining connected even with a few points removed. However, this basic fact leads to a non-trivial property of real and complex polynomials: not all non-constant real polynomials have real roots, but all…
Overview Given a metric on a manifold, it is often necessary to compute its curvature. However, the usual method of first computing the Christoffel symbols and then using those to compute the Riemann curvature tensor is tedious and error-prone. Fortunately, there’s another way to compute the curvature that’s often quicker and easier: Cartan’s method of moving frames, or the…
1. Overview This article explains Reed-Solomon erasure codes and the problems they solve in gory detail, with the aim of providing enough background to understand how the PAR1 and PAR2 file formats work, the details of which will be covered in future articles. I’m assuming that the reader is familiar with programming, but has not had much exposure to coding theory or linear algebra. Thus,…
. --> (This was discussed on r/math and Hacker News .) 1. Overview In this article, I hope to convince you that the quintic equation is unsolvable, in the sense that I can’t write down the solution to the equation \[ ax^5 + bx^4 + cx^3 + dx^2 + ex + f = 0 \] using only addition, subtraction, multiplication, division, raising to an integer power, and taking an integer root. In fact, I hope to…
1. The algorithm Today I’m going to talk about the generalization of the integer square root algorithm to higher roots. That is, given \(n\) and \(p\), computing \(\iroot(n, p) = \lfloor \sqrt[p]{n} \rfloor\), or the greatest integer whose \(p\)th power is less than or equal to \(n\). The generalized algorithm is straightforward, and it’s easy to generalize the proof of correctness,…
(Note: this article is a summary of this thread on ompf2 .) The usual method for sampling a sphere from a point outside the sphere is to calculate the angle of the cone of the visible portion and uniformly sample within that cone, as described in Shirley/Wang . However, one detail that is glossed over is that you still need to map from the sampled direction to the point on the sphere. The usual…
1. The algorithm Today I’m going to talk about a fast algorithm to compute the integer square root of a non-negative integer \(n\), \(\isqrt(n) = \lfloor \sqrt{n} \rfloor\), or in words, the greatest integer whose square is less than or equal to \(n\). [1] Most sources that describe the algorithm take it for granted that it is correct and fast. This is far from obvious! So I will prove both…
1. Overall method Finding the most significant set bit of a word (equivalently, finding the integer log base 2 of a word, or counting the leading zeros of a word) is a well-studied problem . Bit Twiddling Hacks lists various methods, and Wikipedia gives the CPU instructions that perform the operation directly. However, all of these methods are either specific to a certain word size or take more…
(Note: this article isn't fully polished yet, but I thought it would be a shame to let it languish during my sabbatical. Happy new year!) 5. Strengthening the AKS theorem It turns out the conditions of the AKS theorem are stronger than they appear; they themselves imply that \(n\) is prime. To show this, we need the following theorem, which we'll state without proof: ( Lenstra's squarefree test .)…
1. Introduction Exactly ten years ago, Agrawal , Kayal , and Saxena published “PRIMES is in P” , which described an algorithm that could provably determine whether a given number was prime or composite in polynomial time. The AKS algorithm is quite short, but understanding how it works via the proofs in the paper requires some mathematical sophistication. Also, some results in the last…
I will explain two commonly-used primality tests: Fermat and Miller-Rabin. Along the way, I will cover the basic concepts of primality testing. I won't be assuming any background in number theory, but familiarity with modular arithmetic will be helpful. I will also be providing implementations in Javascript, so familiarity with it will also be helpful. Finally, since Javascript doesn't natively…
While recently reviewing some topics in vector calculus, I became curious as to why violating seemingly innocuous conditions for some theorems leads to surprisingly wild results. In fact, I was struck by how these theorems resemble computer programs, not in some abstract way , but in how the lack of “input validation” leads to non-obvious behavior in the face of erroneous input. I…
While reading about proper tail recursion in Scheme, I encountered a similar but obscure optimization called evlis tail recursion . In the paper where it was first described , the author claims it "dramatically improve the space performance of many programs," which sounded promising. However, the few places where its mentioned don't do much more than state its definition and claim its usefulness.…
While reading Timothy Gowers's blog I stumbled on Scott Carnahan's comment describing an elegant calculation of the Gaussian integral \[ ∫_{-∞}^{∞} e^{-x^2} \, dx = \sqrt{π}\text{.} \] I was so struck by its elementary character that I imagined what it would be like written up, say, as an extra credit exercise in a single-variable calculus class: Exercise 1. ( The Gaussian integral .) Let \[ F(t)…
One thing I noticed ever since getting a multi-core system was that the reference FLAC encoder is not multi-threaded. This isn't a huge problem for most people as you can simply encode multiple files at the same time but I usually rip my audio CDs into a single audio file with a cue sheet instead of separate track files and so I am usually encoding a single large audio file instead of multiple…
Okay, I lied; you can't really embed brainfuck in C++ but you can get pretty close. Here is an example: #include "bfpp.h" int main() { // Prints out factorial numbers in sequence. Adapted from // http://www.hevanet.com/cristofd/brainfuck/factorial.b . bfpp * + + + + + + + + + + * * * + * + -- * * * + -- - -- & & & & & -- + & & & & & ++ * * -- -- - ++ * -- & & + * + * - ++ & -- * + & - ++ & -- * +…
Another interesting problem I stumbled across on reddit is finding the longest substring of a given string that is a palindrome. I found the explanation on Johan Jeuring's blog somewhat confusing and I had to spend some time poring over the Haskell code (eventually rewriting it in Python) and walking through examples before it "clicked." I haven't found any other explanations of the same approach…
I encountered an interesting problem on reddit a few days ago which can be paraphrased as follows: Find a perfect square \(s\) such that \(1597s + 1\) is also perfect square. After reading the discussion about implementing a brute-force algorithm to solve the problem and spending a futile half-hour or so trying my hand at find a better way, someone noticed that the problem was an instance of…