Hacker News with Generative AI: Algorithms

Bluesky is ushering in a pick-your-own algorithm era of social media (newscientist.com)
More than 20 million people have joined Bluesky, a social network that gives you fine-grained control over what you see and who you interact with. I think it is the future of social media, says Chris Stokel-Walker

Social Media, Algorithms, User Experience, Technology

184 points by amichail 18 hours ago | 233 comments

AAA – Analytical Anti-Aliasing (frost.kiwi)
Today’s journey is Anti-Aliasing and the destination is Analytical Anti-Aliasing. Getting rid of rasterization jaggies is an art-form with decades upon decades of maths, creative techniques and non-stop innovation. With so many years of research and development, there are many flavors.

Graphics, Computer Graphics, Anti-Aliasing, Algorithms

503 points by todsacerdoti 23 hours ago | 74 comments

Understanding the BM25 full text search algorithm (emschwartz.me)
BM25, or Best Match 25, is a widely used algorithm for full text search. It is the default in Lucene/Elasticsearch and SQLite, among others. Recently, it has become common to combine full text search and vector similarity search into "hybrid search". I wanted to understand how full text search works, and specifically BM25, so here is my attempt at understanding by re-explaining.

Search Engines, Algorithms, Text Search, Computer Science

283 points by rrampage 1 day ago | 54 comments

Understanding the BM25 full text search algorithm (emschwartz.me)
BM25, or Best Match 25, is a widely used algorithm for full text search. It is the default in Lucene/Elasticsearch and SQLite, among others. Recently, it has become common to combine full text search and vector similarity search into "hybrid search". I wanted to understand how full text search works, and specifically BM25, so here is my attempt at understanding by re-explaining.

Search Engines, Algorithms, Information Retrieval

10 points by emschwartz 2 days ago | 1 comments

Bit-twiddling optimizations in Zed's Rope (zed.dev)
A couple of weeks ago I came across one of Antonio's PRs, titled "Speed up point translation in the Rope" — now who doesn't stop to take a closer look at a PR with that title?

Optimization, Programming, Software, Algorithms

107 points by misternugget 3 days ago | 38 comments

Phonetic Matching (smoores.dev)
Just as heads up: This post starts out somewhat technical and includes a discussion of interesting algorithmic topics, like forced alignment and phonetic matching. But it ends by delving into some deeper social and human topics that might not be what everyone is looking for in a blog that’s mostly about software.

Algorithms, Software, Linguistics, Social Issues, Forced Alignment

76 points by raybb 3 days ago | 36 comments

ChibiHash: Small, Fast 64 bit hash function (nrk.neocities.org)
If you need a small and fast 64 bit hash function that can be copy-pasted easily, then here's one that I cooked up in an hour or so: chibihash64.h.

Cryptography, Algorithms, Programming, Hash Functions, Code

103 points by thunderbong 3 days ago | 31 comments

ChibiHash: Small, Fast 64 bit hash function (nrk.neocities.org)
If you need a small and fast 64 bit hash function that can be copy-pasted easily, then here's one that I cooked up in an hour or so: chibihash64.h.

Hash Functions, Programming, Software, Algorithms

4 points by bratao 4 days ago | 0 comments

Tiling with Three Polygons Is Undecidable (arxiv.org)
We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of the three polygons (either allowing or forbidding reflections)? This result improves on the best previous construction which requires five polygons.

Mathematics, Computational Geometry, Algorithms, Theory, Undecidability

132 points by denvaar 4 days ago | 26 comments

Histogramming Bytes with Positional Popcount (blogspot.com)
A while ago, after some back and forth on twitter/X with @corsix, I dropped some implementation of byte histogramming without explaining anything. This post aims to rectify that lack of explanation.

Programming, Data Structures, Algorithms, Optimization

46 points by jandrewrogers 7 days ago | 0 comments

Show HN: Stretch My Time Off – An Algorithm to Optimize Your Vacation Days (stretchmytimeoff.com)
In , there are 0 public holidays in 2024. Let's stretch your time off from 0 days to 0 days (how?)

Productivity, Algorithms, Time Management

358 points by zachd 9 days ago | 174 comments

Is the UK's liver transplant matching algorithm biased against younger patients? (aisnakeoil.com)
Predictive algorithms are used in many life-or-death situations. In the paper Against Predictive Optimization, we argued that the use of predictive logic for making decisions about people has recurring, inherent flaws, and should be rejected in many cases.

Healthcare, Algorithms, Bias, Ethics

93 points by randomwalker 9 days ago | 62 comments

The CVM Algorithm (buttondown.com)
Everything you need to know about query planning can be understood from this query:

Algorithms, Databases, Query Optimization

13 points by todsacerdoti 10 days ago | 1 comments

How Chordcat works – a chord naming algorithm (s20n.dev)
chordcat is a chord-naming application and a pet project of mine. It is written in C++ and SFML.

Music, Algorithms, Software, Programming, C++

125 points by lapnect 10 days ago | 105 comments

The Postage Stamp Problem (johndcook.com)
I recently stumbled upon the Postage Stamp Problem. Given two relatively prime positive numbers a and b, show that any sufficiently large number N, there exists positive integers x and y such that

Mathematics, Number Theory, Algorithms

6 points by azhenley 10 days ago | 0 comments

Diffusion models are evolutionary algorithms (gonzoml.substack.com)
Authors: Yanbo Zhang, Benedikt Hartl, Hananel Hazan, Michael Levin Paper: https://arxiv.org/abs/2410.02543 Code: https://github.com/Zhangyanbo/diffusion-evolution

Generative AI, Machine Learning, Artificial Intelligence, Algorithms

126 points by che_shr_cat 11 days ago | 27 comments

Turing kicked us out of Heaven (2023) (buttondown.com)
The halting problem is "undecidable": there's no algorithm which can tell you if an arbitrary program with an arbitrary input will halt or not. IE, if you give me a proposed "halt-detector", I can inspect it and come up with a program and input for which it would give the wrong answer.

Computer Science, Algorithms, Theory

34 points by todsacerdoti 15 days ago | 42 comments

Languages ... by finite semigroups [generalised to] trees and graphs (2020)[pdf] (mimuw.edu.pl)

Mathematics, Computer Science, Algorithms, Graph Theory

28 points by 082349872349872 17 days ago | 0 comments

Question Sets and All Paths (andrewpwheeler.com)
I was nerd-sniped with a question at work the other day. The set up was like this, imagine a survey where all of the questions have yes-no answers. Some of the answers are terminating, so if you answer No to a particular question, the questions stop. But some if you reach that part of the tree will keep going.

Algorithms, Logic, Programming

5 points by apwheele 19 days ago | 5 comments

The Monkey and the Coconuts: An Introduction to the Extended Euclidean Algorithm (github.com/WinVector)

Mathematics, Algorithms, Programming, Computer Science

19 points by jmount 19 days ago | 1 comments

Consistently faster and smaller compressed bitmaps with Roaring (2016) (arxiv.org)
Compressed bitmap indexes are used in databases and search engines.

Databases, Search Engines, Data Compression, Performance Optimization, Algorithms

54 points by hambandit 20 days ago | 8 comments

Demystifying the regular expression that checks if a number is prime (2016) (illya.sh)
A while back I was researching the most efficient way to check if a number is prime. This lead me to find the following piece of code:

Programming, Algorithms, Mathematics, Optimization, Regular Expressions

159 points by aquir 21 days ago | 47 comments

How to Correctly Sum Up Numbers (cedardb.com)
One of the first examples for loops in probably every programming language course is taking a list of numbers and calculating the sum of them.

Programming, Algorithms, Data Structures

41 points by sebg 21 days ago | 44 comments

Sorting for Rendering (linebender.org)
Many rendering algorithms (including a proposed sparse strip technique for path rendering, and also Gaussian Splatting) rely on sorting. Because the GPU has a different architecture to the CPU, programs running on the GPU have different performance characteristics, and this changes which sorting algorithms are optimal for a particular context. In particular, sorting algorithms that exploit parallelism tend to be more suited to the GPU.

Rendering, Algorithms, GPU Optimization, Computer Graphics

7 points by matt_d 21 days ago | 0 comments

Show HN: Super Simple CRC32 Implementation (github.com/dch82)
super simple crc32 calculator written by dch82

Software, Algorithms, Code, Cryptography

14 points by dch82 23 days ago | 16 comments

Nested Loops Revisited Again (2023) (ieee.org)

Algorithms, Programming, Computer Science

40 points by feeblefakie 24 days ago | 5 comments

Grokking Algorithms: An illustrated guide for programmers and curious people [pdf] (anarcho-copy.org)

Algorithms, Programming, Computer Science, Books, Education

34 points by thunderbong 24 days ago | 7 comments

Can a Rubik's Cube be brute-forced? (stylewarning.com)
When I was about 13, while still a middle-schooler, I became fascinated with the Rubik’s Cube1. I never got terribly good at solving it, maybe eventually getting into the 30 to 40 seconds range. While I didn’t have a penchant for memorizing move sequences, I was drawn into how we find these move sequences.

Puzzles, Algorithms, Rubik's Cube

61 points by lispybanana 24 days ago | 40 comments

Amanatides and Woo's fast voxel traversal (m4xc.dev)
In this article we will dive deep into Amanatides and Woo's fast voxel traversal algorithm. Designed for, however not limited to, ray tracing voxel grids.