751
Damn Cool Algorithms: Cardinality Estimation
Posted by Nick Johnson | Filed under python , cardinality-estimation , damn-cool-algorithms
Topics /
Math & Algorithms
The most popular blog posts about math & algorithms on Hacker News. 2,851 posts.
752
Progress toward fusion energy gain as measured against the Lawson criteria
Today we’ve released a pre-publication version of an update to our 2022 paper “Progress toward fusion energy breakeven and gain as measured against the...
753
Proof-Of-Work is a Decentralized Clock
This is an explanation of the key function on Proof-of-Work in the Bitcoin blockchain. It focuses on the one feature of Proof-of-Work that is essential and shows that other features often talked about such as security are secondary side-effects, useful, but not essential. This explanation rests on illustrating a few…
754
We have proof automation now
I've long had a soft spot for dependently-typed languages like Coq Rocq and Lean. They offer the possibility of a type system capable of encoding and enforcing arbitrarily subtle invariants. The sort of thing that, in regular languages, ends up (at best) as a comment, and which quickly gets lost as the size of the…
755
Building a data compression utility in Haskell using Huffman codes
In this post we will implement a data compression program in about 150 lines of Haskell. It will use Huffman coding and handle arbitrary binary files using constant memory for encoding and decoding.
756
A tutorial quantum interpreter in 150 lines of Lisp
a personal blog
757
Faster than earcut: triangulating 3.7M map polygons in 489 ms
We published the triangulator of our map engine as earstrip, an ISC-licensed C++ and WebAssembly library. How it came to be: the ear clipper rebuilt one idea at a time and timed on 3.7 million polygons of real map data.
758
759
Ice
Water is complicated and fascinating stuff! There are at least sixteen known crystal phases of ice, many shown in this diagram based on the work of Martin Chaplin: (Click for a larger version.) For…
760
Math Academy pulled me out of the Valley of Despair
Here’s to being a preserving student for life.
761
How to Fold a Julia Fractal
A tale of numbers that like to turn: a different look at complex numbers and the strange things they do.
762
First improvement of fundamental algorithm in 10 years
The max-flow problem, which is ubiquitous in network analysis, scheduling, and logistics, can now be solved more efficiently than ever.
763
About the supposed factoring of a 4096 bit RSA key
This blog is written by Hanno Böck. Unless noted otherwise, its content is licensed as CC0 .
764
Fast midpoint between two integers without overflow
Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number. With each guess, I tell you whether your guess is correct, smaller or larger than my number. A binary search algorithm tries to find a value in an interval by repeating … Continue reading Fast…
765
Apple’s M1 processor and the full 128-bit integer product
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…
766
The Curious Case of MD5
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.
767
768
Using a Markov chain to generate readable nonsense with 20 lines of Python
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.
769
770
Prediction Markets: When Do They Work?
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…
771
Convolutions, Fast Fourier Transform and polynomials (2022)
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…
772
29-year-old Conway conjecture settled
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…
773
Possibly all the ways to get loop-finding in graphs wrong
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…
774
An Introduction to Geometric Algebra
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…
775
Generating SVG for the prime knots
How I created a wall poster of knot diagrams.
776
Designing a Tree Diff Algorithm Using Dynamic Programming and A*
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…
777
Poor Foundations in Geometric Algebra
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…
778
Number of legal 18x18 Go positions computed. One more to go
L19 = 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
779
There's Math.random(), and then there's Math.random()
V8’s Math.random implementation now uses an algorithm called xorshift128+, improving the randomness compared to the old MWC1616 implementation.
780
You're doing it wrong: B-heap 10x faster than binary heap (2010)
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 ?