Notes concerning “Algorithms”

• A cute algorithm for card-image templates 2007 to 2009 (2 minutes)
• Additive smoothing for Markov models 2007 to 2009 (updated 2019-05-19) (11 minutes)
• Worst-case-logarithmic-time reduction over arbitrary intervals over arbitrary semigroups 2012-12-04 (5 minutes)
• a logarithmic-time alternative to summed-area tables for reducing arbitrary semigroup operations over arbitrary ranges (a generalization of RMQ segment trees) 2012-12-06 (updated 2013-05-17) (10 minutes)
• Alastair thesis review 2013-05-17 (1 minute)
• Use crit-bit trees as the fundamental string-set data structure 2013-05-17 (3 minutes)
• Cycle sort 2013-05-17 (1 minute)
• Quadtree compression of terminal video RAM to do a megapixel windowing system in 6 KiB 2013-05-17 (9 minutes)
• Distinguishing natural languages with 3-grams of characters 2013-05-17 (updated 2013-05-20) (7 minutes)
• Constant-space grep 2014-02-24 (3 minutes)
• Simple persistent in-memory dictionaries with log² lookups and logarithmic insertion 2014-02-24 (6 minutes)
• Square wave synthesis 2014-02-24 (2 minutes)
• Compression with second-order diffs 2014-04-24 (3 minutes)
• Precisely how is 3 “optimal” for one-hot state machines, sparse FIR kernels, etc.? 2014-04-24 (8 minutes)
• Polynomial-spline FIR kernels by integrating sparse kernels 2014-04-24 (12 minutes)
• Randomizing delta-sigma conversion to eliminate aliasing 2014-04-24 (7 minutes)
• Some speculative thoughts on DSP algorithms 2014-04-24 (20 minutes)
• Rendering iterated function systems (IFSes) with interval arithmetic 2014-09-02 (6 minutes)
• You can’t sort a file whose size is cubic in your RAM size in two passes, only quadratic 2015-05-28 (5 minutes)
• Editor buffers 2015-07-15 (updated 2015-09-03) (16 minutes)
• Cobstrings 2015-08-21 (updated 2015-08-31) (5 minutes)
• Parsing a conservative approximation of a CFG with a FSM 2015-09-03 (7 minutes)
• Incremental MapReduce for Abelian-group reduction functions 2015-09-03 (4 minutes)
• Rhythm codes 2015-09-03 (4 minutes)
• Ternary mergesort 2015-09-03 (2 minutes)
• Very fast FIR filtering with time-domain zero stuffing and splines 2015-09-03 (updated 2015-09-07) (13 minutes)
• Convolution surface plotting 2015-09-03 (updated 2015-09-13) (2 minutes)
• Convolution applications 2015-09-07 (updated 2019-08-14) (9 minutes)
• Interval filters 2015-09-17 (2 minutes)
• Hash gossip exchange 2015-11-19 (4 minutes)
• Improving LZ77 compression with a RET bytecode 2016-04-05 (updated 2016-04-06) (3 minutes)
• Trees as code 2016-05-10 (4 minutes)
• Gaussian spline reconstruction 2016-06-05 (updated 2016-06-06) (5 minutes)
• Improving lossless image compression with basic machine learning algorithms 2016-07-27 (2 minutes)
• Append only unique string pool 2016-07-27 (2 minutes)
• Algorithm time capsule 2016-08-11 (1 minute)
• Internal determinism 2016-08-17 (2 minutes)
• Robust hashsplitting with sliding Range Minimum Query 2016-09-05 (7 minutes)
• Intro to algorithms 2016-09-06 (4 minutes)
• An almost-in-place mergesort 2016-09-07 (5 minutes)
• Gradient rendering 2016-09-24 (11 minutes)
• Counting the number of spaces to the left in parallel 2016-10-11 (5 minutes)
• What’s the dumbest register allocator that might give you reasonable performance? 2016-10-11 (15 minutes)
• Chintzy depth of field 2016-10-27 (1 minute)
• Bitsliced operations with a hypercube of shuffle operations 2016-11-30 (2 minutes)
• The paradoxical complexity of computing the top N 2017-01-04 (7 minutes)
• Using Aryabhata’s pulverizer algorithm to calculate multiplicative inverses in prime Galois fields and other multiplicative groups 2017-01-06 (updated 2019-07-05) (4 minutes)
• Constant time sets for pixel painting 2017-02-07 (2 minutes)
• Wang tile addition 2017-02-16 (3 minutes)
• Set hashing 2017-03-09 (9 minutes)
• Amnesic hash tables for stochastically LRU memoization 2017-04-03 (1 minute)
• Incremental persistent binary array sets 2017-04-10 (4 minutes)
• String tuple encoding 2017-04-28 (2 minutes)
• ASCIIbetically homomorphic encodings of general data structures 2017-06-15 (2 minutes)
• Golomb-coding operands as belt offsets likely won’t increase code density much 2017-06-15 (updated 2017-06-20) (6 minutes)
• CIC-filter fonts 2017-06-28 (1 minute)
• Can you make a vocoder simpler using CIC filters? 2017-06-28 (updated 2018-06-17) (2 minutes)
• Binary translation register maps 2017-07-19 (1 minute)
• Double heap sequence 2017-07-19 (2 minutes)
• Rasterizing polies 2017-07-19 (3 minutes)
• A tournament to decide which notes to devote attention to polishing 2017-07-19 (2 minutes)
• Vectorized prefix sum 2017-07-19 (5 minutes)
• Multiplication with squares 2017-07-19 (updated 2019-07-09) (5 minutes)
• Another candidate lightweight frequency tracking algorithm 2017-08-18 (4 minutes)
• Cassette tape capacity 2018-04-27 (1 minute)
• Incremental recomputation 2018-04-27 (12 minutes)
• Gradient descent beyond machine learning 2018-05-18 (2 minutes)
• Accelerating convolution and correlation with short periodic waveforms using OLAP marginal prefix sums 2018-06-05 (4 minutes)
• Is a phase vocoder or a bunch of PLLs a more efficient way to listen to all FM radio stations at once? 2018-06-17 (updated 2019-07-29) (7 minutes)
• Top algorithms 2018-07-29 (4 minutes)
• Bit difference array 2018-10-28 (10 minutes)
• Quintic upsampling of time-series with 1½ multiplies per sample 2018-10-28 (2 minutes)
• Digital noise generators 2018-10-28 (2 minutes)
• Cheap textures 2018-10-28 (updated 2019-05-05) (5 minutes)
• Dilating letterforms 2018-11-04 (15 minutes)
• Gauzy shit 2018-11-04 (4 minutes)
• The Bleep ultrasonic modem for local data communication 2018-12-10 (updated 2018-12-11) (8 minutes)
• Improving Lua #L with incremental prefix sum in the ∧ monoid 2018-12-18 (7 minutes)
• Matrix exponentiation linear circuits 2018-12-18 (4 minutes)
• Evaluating DSP operations in minimal buffer space by pipelining 2018-12-18 (updated 2018-12-19) (20 minutes)
• Sample reversal 2018-12-18 (updated 2019-01-17) (5 minutes)
• Real-time bokeh algorithms, and other convolution tricks 2018-12-18 (updated 2019-08-15) (23 minutes)
• Some notes on morphology, including improvements on Urbach and Wilkinson’s erosion/dilation algorithm 2019-01-04 (updated 2019-11-12) (26 minutes)
• Median filtering 2019-01-17 (11 minutes)
• Hardware multiplication with square tables 2019-02-08 (updated 2019-07-09) (4 minutes)
• Tabulating your top event of the month efficiently using RMQ algorithms 2019-03-19 (8 minutes)
• Accelerating Euler’s Method on linear time-invariant systems by exponentiating matrices 2019-03-24 (updated 2019-04-02) (7 minutes)
• Karatsuba 2019-04-20 (2 minutes)
• Granite texture 2019-05-08 (updated 2019-05-09) (5 minutes)
• A language whose memory model is a bunch of temporally-indexed logs 2019-05-12 (updated 2018-05-21) (20 minutes)
• Image approximation 2019-05-14 (10 minutes)
• Profile-guided parser optimization should enable parsing of gigabytes per second 2019-05-23 (8 minutes)
• Things in Dercuano that would be big if true 2019-05-24 (updated 2019-08-21) (24 minutes)
• Midpoint method texture mapping 2019-06-01 (3 minutes)
• Smooth hysteresis 2019-06-11 (13 minutes)
• Using the Goertzel algorithm, the Minsky algorithm, PLLs, and prefix sums for frequency detection 2019-06-16 (updated 2019-07-05) (39 minutes)
• Reducing the cost of self-verifying arithmetic with array operations 2019-06-23 (15 minutes)
• Fermat primes 2019-07-07 (4 minutes)
• Using the method of secants for general optimization 2019-07-22 (updated 2019-11-26) (13 minutes)
• $1 recognizer diagrams 2019-08-11 (updated 2019-10-24) (15 minutes)
• The miraculous low-rank SVD approximate convolution algorithm 2019-08-14 (updated 2019-08-15) (31 minutes)
• Complex linear regression (in the field ℂ of complex numbers) 2019-08-17 (updated 2019-08-18) (9 minutes)
• Robust local search in vector spaces using adaptive step sizes, and thoughts on extending quasi-Newton methods 2019-08-17 (updated 2019-09-15) (15 minutes)
• Query evaluation with interval-annotated trees over sequences 2019-08-30 (updated 2019-09-03) (30 minutes)
• Differentiable neighborhood regression 2019-08-31 (15 minutes)
• Image filtering with an approximate Gabor wavelet or Morlet wavelet using a cascade of sparse convolution kernels 2019-08-31 (updated 2019-09-08) (28 minutes)
• Cloth structure from shading 2019-09-01 (2 minutes)
• Processing halftoning 2019-09-01 (15 minutes)
• Debokehfication 2019-09-01 (updated 2019-09-12) (4 minutes)
• Isotropic nonlinear texture effects for letterforms from a scale-space representation 2019-09-10 (16 minutes)
• Nonlinear bounded leaky integrator 2019-09-11 (8 minutes)
• Fast mathematical optimization with affine arithmetic 2019-09-15 (5 minutes)
• An affine-arithmetic database index for rapid historical securities formula queries 2019-09-15 (15 minutes)
• Sparse sinc 2019-09-15 (10 minutes)
• B-Tree ropes 2019-09-24 (updated 2019-09-25) (19 minutes)
• Is there an incremental union find algorithm? 2019-10-01 (8 minutes)
• Negative weight undirected graphs 2019-11-01 (8 minutes)
• Sparse filter optimization 2019-11-01 (5 minutes)
• Interval raymarching 2019-11-02 (updated 2019-11-10) (6 minutes)
• Some thoughts on SDF raymarching 2019-11-11 (updated 2019-12-10) (31 minutes)
• Approximate optimization 2019-11-13 (3 minutes)
• Magic sinewave filter 2019-12-17 (6 minutes)
• Sorting in logic 2019-12-28 (2 minutes)