The latest blog posts to take off on Hacker News. 2,391 posts.
While I was writing the Wolfenstein 3D book [1] , I wanted to demonstrate how much of a handicap it was to work without floating points. My attempts at understanding floating points using canonical [2] articles [3] were met with resistance from my brain. I tried to find a different way. Something far from $(-1)^S *…
Solving systems of linear equations is a staple food of linear algebra. It can be applied as a part of many machine learning tasks, although it is not always...
How many board configurations are there in the game of 2048? Let's estimate using combinatorics.
Edward Tufte’s The Visual Display of Quantitative Information (1998, 2nd edition 2001) is a classic book, arguably his best, and certainly a key text in the field of information graphics (whi…
Consider the following pseudocode: x <- 32; y <- 0; while(true){ x <- x – floor((1/8) * y); y <- y + floor((1/8) * x); plotPointAt(x, y); } x and y are always integers. This draws…
Monoids are a pretty interesting concept in software development. Monoids are everywhere. Monoids are simple yet powerful. And Monoids have a lot to teach us about software, in particular about com…
During my internship at Jane Street 1 , one of my projects was a config editing tool that at first sounded straightforward but culminated in me designing a custom tree diffing algorithm using dynamic programming, relentlessly optimizing it and then transforming it into an A* accelerated path finding algorithm. This…
From the highly eclectic blog of Mark Dominus
In software, we generate random numbers by calling a function called a "random number generator". Such functions have hidden states, so that repeated calls to the function generate new numbers that appear random. If you know this state, you can predict all future outcomes of the random number generators. O'Neill, a…
Anyone who has taken even a cursory glance at the vast menagerie of programming languages should have at least heard the phrase "Hindley-Milner". F#, one of the most promising languages ever to emerge from the forbidding depths of Microsoft Research, makes use of this mysterious algorithm, as do Haskell, OCaml and ML…
Edited 8/16 to correct attributions to Alon and Boppana and to Tardos, thanks to an anonymous commenter for the correction Yesterday, Norbert Blum posted a preprint with a claimed proof that $latex…
This post is about the magic constant 0x5f3759df and an extremely neat hack, fast inverse square root, which is where the constant comes from.
Computers often need random numbers. Most times, random numbers are not actually random... in the sense that they are the output of a mathematical function that is purely deterministic. And it is not even entirely clear what "really random" would mean. It is not clear that we live in a randomized universe... it seems…
Continued from part 1. Once I was about a thousand words into describing background for GEMM, it became pretty clear that it made more sense to group the numerical math papers into one post, so her…
This started out on Twitter and I expected having to write up maybe 50 or so, but then it made the rounds. I don’t think I have 1200+ papers that I’d recommend reading, and even if I di…
Learn Machine Learning (ML) and be ahead of the pack in the Software industry. Machine Learning is a sub-field of Artificial Intelligence (A.I), which is heavily used in modern software systems. Machine Learning algorithms can improve software (a robot) and it's ability to solve problems through gaining experience and…
I recently had a problem where part of the solution was to do a series of pointer accesses that would walk around a chunk of memory in pseudo-random order. Sattolo's algorithm provides a solution to this because it produces a permutation of a list with exactly one cycle, which guarantees that we will reach every…
Andrey Nikolaevich Kolmogorov was one of the giants of 20th-century mathematics. I’ve always found it amazing that the same man was responsible both for establishing the foundations of …
I’ve been talking a lot recently about how quantum algorithms don’t work. But last week JR Minkel, an editor at Scientific American, asked me to write a brief essay about how quantum al…
The Laziest Programmer - Because someone else has already solved your problem.
Heights are normally distributed because height is determined by many factors. But why are other things with many inputs not normally distributed?
One of the saddest and most fascinating things about applied cryptography is how little cryptography we actually use. This is not to say that cryptography isn’t widely used in industry —…
When adding two integers i and j of bitlength b, the result will be of bitlength b + 1 in the worst case. This means they can easily be naively added. If the result is larger or equal to F p one has only to subtract p from the result, i.e.:
