Topics /
The most popular blog posts about math & algorithms on Hacker News. 2,391 posts.
If I multiply two 64-bit integers (having values in [0, 264)), the product requires 128 bits. Intel and AMD processors (x64) can compute the full (128-bit) product of two 64-bit integers using a single instruction (mul). ARM processors, such as those found in your mobile phone, require two instructions to achieve the…
Recently I came across a puzzling fact: the International Criminal Court hashes electronic evidence with MD5, even though MD5 is badly broken. So, why are lawyers using broken, outdated technology? The answer involves the common law system, cultural isolation, and a single man named Don L. Lewis.
Describes a simple Markov chain algorithm to generate reasonable-sounding but utterly nonsensical text, and presents some example outputs as well as a Python implementation.
Epistemic Status: Resident Expert I’m a little late on this, which was an old promise to Robin Hanson (not that he asked for it). I was motivated to deal with this again by the launch of Augu…
You may remember from high school what a polynomial is. If so, you may also remember how to multiply two of them. But what if I told you that the method you were taught is slow as F? In this post we will connect polynomials with the Fourier Transform and convolutions, and show you how to multiply polynomials with…
Ilkka Törmä and Ville Salo, a pair of researchers at the University of Turku in Finland, have found a finite configuration in Conway’s Game of Life such that, if it occurs within a universe a…
In my puzzle collection , there are many games in which you have to connect points together by edges, making a graph, and the puzzle rules say you must avoid making any loop in the graph. Examples are Net , Slant , and some configurations of Bridges (although not the default one). Loopy and Pearl also care about…
Linear Algebra Geometric Algebra Applications Multiplying Vectors Rotors Double Angle Formula Complex Numbers Characterizing B Ratios Conjugates Geometric Algebra is fascinating, and I believe solves a large number of problems that arise from a more traditional approach to vectors, but I've been very disappointed with…
How I created a wall poster of knot diagrams.
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…
EDIT: Be warned that this post is angry. If you’re easily offended when someone goes on a rant, then leave now because I’m very unforgiving in several places below. The tone of my writing is unusually harsh, but the people whose work I’m talking about deserve it, and here’s why. Even though I had been working with…
L19 = 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
Would you believe me, if I claimed that an algorithm which has been on the books as "optimal" for 46 years, which have been analyzed in excruciating detail by geniuses like Knuth and taught in all CS courses in the world, can be optimized to run ten times faster ?
A post about RSA-896.
Tutorials and articles of Inigo Quilez on computer graphics, fractals, math, art, demoscene, shaders and more.
Just days after we celebrated my wife’s 40th birthday, she came down with COVID, meaning she’s been isolating and I’ve been spending almost all my time dealing with our kids. But …
Recently I was doing some work decoding the new Galileo High Accuracy Service data. In short, this new service will allow Galileo (“European GPS”) users to achieve decimeter-level accuracy, which is nice. This “HAS” data is transmitted highly redundantly by making good use of Reed-Solomon encoding. To work with this…
A long division story
Exploiting the quirks of human vision to make images smaller, without looking awful.
Over the past several years I’ve been privileged to observe two contradictory and fascinating trends. The first is that we’re finally starting to use the cryptography that researchers h…
The power to understand and predict the quantities of the world should not be restricted to those with a freakish knack for manipulating abstract symbols.
A new (and better) version of the GOL computer is available here : https://github.com/nicolasloizeau/scalable-gol-computer
Probablistic filters are high-speed, space-efficient data structures that support set-membership tests with a one-sided error. These filters can claim that a given entry is definitely not represented in a set of entries, or might be represented in the set. That is, negative responses are conclusive, whereas positive…
I. Allen Ginsberg’s famous poem on Moloch:What sphinx of cement and aluminum bashed open their skulls and ate up their brains and imagination? Moloch! Solitude! Filth! Ugliness! Ashcans and u…
In software programming, the product between two integers is often computed to a fixed number of bits with overflow. Consider 8-bit integers. If you multiply 127 by 127, you get back the number 1 as an 8-bit unsigned integer, with an overflow. The actual full product is 16129. To represent 16129, you typically use 16…
At the core of the attention mechanism in LLMs are three matrices: Query, Key, and Value. These matrices are how transformers actually pay attention to different parts of the input. In this write-up, we will go through the construction of these matrices from the ground up.
Doga Tekin's website.
Reading maths textbooks linearly doesn't work; here's what to do instead.
