Notes concerning “Prefix sums”

• 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)
• Square wave synthesis 2014-02-24 (2 minutes)
• Compression with second-order diffs 2014-04-24 (3 minutes)
• More thoughts on powerful primitives for simplified computer systems architecture 2015-08-18 (updated 2015-11-02) (165 minutes)
• Efficiently querying a log of everything that ever happened 2015-09-03 (7 minutes)
• Parallel NFA evaluation 2015-09-03 (updated 2015-10-01) (8 minutes)
• Counting the number of spaces to the left in parallel 2016-10-11 (5 minutes)
• Parallel DFA execution 2017-04-18 (9 minutes)
• Vectorized prefix sum 2017-07-19 (5 minutes)
• Accelerating convolution and correlation with short periodic waveforms using OLAP marginal prefix sums 2018-06-05 (4 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)
• Using the Goertzel algorithm, the Minsky algorithm, PLLs, and prefix sums for frequency detection 2019-06-16 (updated 2019-07-05) (39 minutes)
• The miraculous low-rank SVD approximate convolution algorithm 2019-08-14 (updated 2019-08-15) (31 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)
• A bag of candidate techniques for sparse filter design 2019-09-01 (18 minutes)
• Nonlinear bounded leaky integrator 2019-09-11 (8 minutes)