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...
KaTeXMacros = { "\\pd": "\\frac{∂{#1}}{∂{#2}}", "\\CSF": "Γ_{#1}", "\\CS": "{Γ^{#1}}_{#2}", "\\cnf": "{ω^{#1}}_{#2}", "\\crf": "{Ω^{#1}}_{#2}", "\\Riem": "{\\operatorname{Riem}^{#1}}_{#2}", "\\Ric": "\\operatorname{Ric}_{#1}", "\\sgn": "\\operatorname{sgn}", }; div.cheatsheet, div.important-equation { border: 1px solid #002b36;...
KaTeXMacros = { "\\clplus": "\\oplus", "\\clminus": "\\ominus", "\\clmul": "\\otimes", "\\cldiv": "\\oslash", "\\bclmod": "\\mathbin{\\mathrm{clmod}}", }; 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 ...
. --> .graph { display: block; width: 300px; height: 300px; margin: 0.5em 0.2em; } .graph-container { display: inline-block; vertical-align: top; max-width: 300px; } (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...
KaTeXMacros = { "\\iroot": "\\operatorname{iroot}", "\\Bits": "\\operatorname{Bits}", "\\Err": "\\operatorname{Err}", "\\NewtonRoot": "\\mathrm{N{\\small EWTON}\\text{-}I{\\small ROOT}}", }; 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...
(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...
KaTeXMacros = { "\\isqrt": "\\operatorname{isqrt}", "\\Bits": "\\operatorname{Bits}", "\\Err": "\\operatorname{Err}", "\\NewtonSqrt": "\\mathrm{N{\\small EWTON}\\text{-}I{\\small SQRT}}", }; 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) =...
// Converts the given binary string (possibly with whitespace) to an integer. function b(s) { return parseInt(s.replace(/\s+/g, ''), 2); } // Converts the given integer to a binary string. function bs(x) { return x.toString(2); } 1. Overall method Finding the most significant set bit of a word (equivalently, finding the integer log base 2 of...
(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...
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...
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...
KaTeXMacros = { "\\sgn": "\\operatorname{sgn}", }; 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...
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...
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...
/**/ 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...
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 * + + + + + + + + + + * * * + * + -- * * * + -- - -- & & & & & -- + & & & &...
/**/ function trackOutboundLink(url) { ga('send', 'event', 'outbound', 'click', url, { 'hitCallback': function() { document.location = url; } }); } 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...
// See https://github.com/Khan/KaTeX/issues/85 . KaTeXMacros = { "\\cfrac": "\\dfrac{#1}{#2}\\kern-1.2pt", }; 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...