#video of #graphics #algorithms “SIGGRAPH 2026 Papers Fast Forward” #toread (2½ hours)
on 02026-08-25#video of #graphics #algorithms “SIGGRAPH Thesis Fast Forward 2025” #toread (20’)
on 02026-08-25The "FastCDC" #paper explains the #content-defined-chunking #algorithms used by #Nix’s “attic” to deduplicate 64K chunks, published at #USENIX
on 02026-08-19usually reasonable advice: “choose the simplest #algorithms with less than quadratic time and space complexity.” #performance
on 02026-03-18#bzip2 #compression #algorithms can be implemented in a few kilobytes of code, handy for the ComputerCraft mod for #Minecraft. #small-is-beautiful
on 02026-03-12#SIGGRAPH ’24 “thesis fast forward” half-hour #video covering 9 different #graphics dissertations.
Ruben Wiersma talks about applying 2-D neural networks on 3-D meshes in a few different ways, including three that you can pip install: deltaconv pcdiff gravomg.
Chenxi Liu talks about her #algorithms for analyzing vector sketches that artists can use to communicate visual ideas, so far apparently used only for sketch simplification and flood fill.
Rohan Sawhney talks about Monte Carlo geometry processing, specifically to solve PDEs on complex geometry without the volumetric meshing #FEM needs, using “Muller 1956”’s “Walk on Spheres” to interpolate boundary conditions into the interior of a region, using something that sounds similar to an SDF, though he doesn’t call it that; like a “ray tracer” for physics (versus FEM’s “triangle rendering”).
Silvia Sellán talks about faster computation of swept volumes, as well as some other 3-D problems like surface reconstruction; I don’t really understand the common thread between these, though she says it’s “uncertainty quantification”.
Xilong Zhou talks about how to acquire “materials” such as bricks, marble, or ceramic tile, from photos, to use their BRDFs or SVBRDFs in rendering, with some kind of #Bayesian approach.
“Hi, my name is Dr. Zachary Ferguson” talks about a new numerical method for #simulation that don’t experience numerical instability (explosion) when simulated surfaces come into contact and the time step isn’t short enough; it’s called "incremental potential contact", with a new smooth barrier function (with a singularity!) enabling Newton’s method with line search to solve the contact correctly, using continuous collison detection (“CCD”). He claims that his work has “sparked a revolution in physical simulation”, although if that’s true, I don’t know why he feels the need to introduce himself as "Dr. Zachary Ferguson", as if he were used to being ignored and dismissed.
Pascal Guehl [geɪł] talks about texture/material synthesis, what he calls “semi-procedural”, combining the advantages of “by-example” texture synthesis (trying to make things look like a photo) with procedural (adding up noise functions and frequency components). It works by finding the “closest procedural model” to a given example image. Looks really cool.
S. Mazdak “Maz” Abdulnaga talks about volumetric mapping for medical imaging, in particular by minimizing the distortion energy of a volumetric map (ℝ³ → ℝ³) between two target volumes; the energy is defined in a symmetric way, so it doesn’t change when you swap the volumes. For example, you can use this to analyze placental health during pregnancy by mapping 3-D MRI scans taken over time to one another. Other applications include improving texture transfer for surfaces.
Yiwei Hu talks about “efficient material authoring by inverse material modeling”, tackling the same problem as Pascal Guehl in more or less the same way, but using CNN #neural-networks and gradient-based #optimization; his approach seems to handle some cases like checkerboard patterns better than Guehl’s.
on 02026-01-14#D-star #path-planning #algorithms “widely used for mobile robot and autonomous vehicle navigation”
on 02026-01-14#Bezier curves with de Casteljau’s #algorithms by #Wildberger. #video #toread
on 02026-01-13#skeletonization #algorithms explained in Steven Skiena’s “Stony Brook Algorithms Repository”
on 02026-01-12Felzenszwalb and Huttenlocher’s #PDF #paper DOI:10.4086/toc.2012.v008a019 on simple #algorithms for calculating the Euclidean #distance-transform of a pixmap: “Distance Transforms of Sampled Functions.”
Abstract: We describe linear-time algorithms for solving a class of problems that involve transforming a cost function on a grid using spatial information. These problems can be viewed as a generalization of classical distance transforms of binary images, where the binary image is replaced by an arbitrary function on a grid. Alternatively they can be viewed in terms of the minimum convolution of two functions, which is an important operation in grayscale morphology. A consequence of our techniques is a simple and fast method for computing the Euclidean distance transform of a binary image. Our algorithms are also applicable to Viterbi decoding, belief propagation, and optimal control.
on 02026-01-12Steven #Wittens’s #SDF #fonts page where he implemented the Euclidean #Distance-Transform to avoid the #Mapbox #TinySDF wobbliness and pixelation problems. Apparently there’s a separable approach to this: “Like a Fourier Transform, you can apply it to 2D images by applying it horizontally on each row X, then vertically on each column Y (or vice versa).” ...really? Holy shit, you just count up with squared distances and everything works, that’s fucking insane. Then he figures out how to make it work with subpixel #antialiasing: “Here’s how I assembled a “true” Euclidean Subpixel Distance Transform.” #algorithms #toread
on 02026-01-12#video on Euclidean #distance-transform #algorithms #toread
on 02026-01-09GitHub repo covering 11 #sliding-window-aggregation #algorithms: DABA, DABA Lite, FiBA, FlatFIT, IOA, Two-Stacks, Two-Stacks Lite, Reactive, Recalc (just recalculating the aggregation from scratch), SOE (subtract on evict), AMT (amortized monoid tree aggregator), etc.
on 02026-01-06#PDF #paper #toread on #sliding-window-aggregation #algorithms, a generalization of #RMQ
on 02026-01-06improving perfect #hashing #algorithms
on 02025-11-11#video on a variant of #surface-stable fractal #dithering #algorithms
on 02025-10-29DDJ’s copy of Mark Nelson’s DDJ article on #BWT #compression. #algorithms
on 02025-10-10#Ryg’s article on #BWT #compression. #algorithms
on 02025-10-10Mark Nelson’s DDJ article on #BWT #compression. #algorithms
on 02025-10-10linear-probing #hashing that tries to keep probe sequences short by fancy insertion? #performance #algorithms #toread
on 02025-09-11#video of a talk by Kulukundis at cppcon 2017. Kip says, “Presentation about the latest tricks in hash tables. Uses SSE instructions and man is it fast. Good benchmarks against the standard C routines.” Heh: “As with anything like this, benchmarks are the only source of truth you will ever get, and they are lies.” Called "Swiss tables" (because Alkis and Roman, its primary developers, “are in the Zurich office”, and it’s “closed hashing”), supposedly the fastest hash table in the world. “What did we gain? (...) the vague feeling of superiority when we force a difficult decision onto the user. And that is the #C++ way.” You put metadata about which array elements are full or deleted into a separate byte array, along with truncated-to-7-bits hash values, to avoid needing magic sentinel values for your key type. By using SSE matching to look for truncated-hash matches in a 16-bucket group, you can find the candidates in three instructions, which also means that your erase function can avoid inserting tombstones “if any other element in the group was empty”, which seems like a pretty big win actually. Also he mentions “other sizes [than power of 2] with fast modulus”. #algorithms #performance #hashing
on 02025-09-06#PDF of Park and Chin’s 01997 #paper on optimal #morphology #algorithms for a certain class of decomposable kernels #toread
on 02025-08-27explanation of #CORDIC #algorithms in bullet-point fashion with some 8-bit code #toread
on 02025-08-27#history of #McIlroy’s spell checker: Rice-coding a Golomb ruler for the dictionary. #algorithms
on 02025-08-1201994 #paper by Xinhua Zhuang, “Decomposition of Morphological Structuring Elements” about “two-pixel decomposition” and “cellular decomposition” in #morphology #algorithms for #performance
on 02025-08-12the #skimage #morphology module is using #algorithms that are optimal for hardware accelerators nobody uses
on 02025-08-12Xiaolin Wu’s line-drawing algorithm, with purportedly correct code, but using Win32 DrawPixel. #graphics #algorithms
on 02025-08-06fmt does #word-wrap with #dynamic-programming or similar #optimization #algorithms
on 02025-07-27Гео́ргий Макси́мович Адельсо́н-Ве́льский, who invented the AVL tree with Evgenii Landis in 01962‚ retired to Israel in 01992 and died in 02014. #algorithms #history
on 02025-07-24#PDF of Knuth’s 01986 #paper where he presents #hash-tries #algorithms #history
on 02025-07-2464 bytes of ASCII to lowercase in three instructions: __m512i ca = _mm512_sub_epi8(c, _mm512_set1_epi8('A')); __mmask64 is_upper = _mm512_cmple_epu8_mask(ca, _mm512_set1_epi8('Z' - 'A')); __m512i to_lower = _mm512_mask_add_epi8(c, is_upper, c, to_lower) from Daniel Lemire’s talk on designing #algorithms for #performance on current hardware
“In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.” #algorithms #optimization
on 02025-07-19“A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees.” The Lengauer–Tarjan algorithm #paper from 01979. #toread #compilers #graphs #algorithms “A vertex v dominates another vertex w≠v in G if every path from [the start vertex] r to w contains v.”
on 02024-12-12“Dominance is one of the most ubiquitous concepts in #compilers. By far the most popular algorithm for discovering dominance relationships is the Lengauer-Tarjan algorithm - a fascinating but scary piece of genius. In this article, we will deconstruct its most important part, the computation of semidominators. To tackle it, I’ll use a lot of intuition, crappy drawings and some imagination.” #toread #algorithms #Baziotis
on 02024-12-12#convolution #algorithms using polynomial multiplication for Transformer #neural-networks, going back and forth between the coefficient representation of a polynomial and value representations of it, especially evaluating it at n+1 complex roots of unity. #math #toread
on 02024-12-12discussion of #convolution #algorithms including some ideas from compressed sensing etc.
on 02024-12-12application of binary search #algorithms in checking CCTV footage for bicycle theft
on 02024-12-12animated explanation of #Skyline #algorithms for online 2-D bin packing, mentioning the MAXRECTS alternative
on 02024-11-18discussion of #Skyline #algorithms for 2-D bin packing, and alternatives
on 02024-11-18#Hashing #algorithms in the CPython dict implementation; by adding a level of indirection to the (hashval, key, value) tuples, you can greatly reduce the amount of space used, thus improving #performance. As a side effect, you can iterate over entries in insertion order.
on 02024-08-31discussion of #sorting #algorithms #performance and cmov
open-access #ebook under an MIT license, a textbook on #algorithms and data structures
on 02024-08-21a comparison of #hashing #algorithms #performance in 02012
on 02024-08-20discussion from 01991 of #hashing #algorithms on comp.lang.c between Henry Spencer (who says C News could just as well have used strlen() like PHP later did), Chris Torek, Dan Bernstein, Dave Harris, Richard Harter, Rich Salz, Phong Vo, et al. Title “hash function for mac needed”.
on 02024-08-20The so-called "djb2" hash function is indeed by Dan Bernstein, but it’s from 01991: hash = 5381; while ((c = *s++)) h = (h << 5) + h + c; #hashing #algorithms
#graphics #algorithms for median filtering and percentile filtering (rank filters): the histogram algorithm, binary-tree algorithm, Perreault and Hérbert’s constant-time algorithm, etc.
on 02024-07-27discussion of #graphics #algorithms for median filtering
on 02024-07-27#video #toread of sorting #algorithms visualized with discrepancy chords (from each value’s current position on the circle to its ideal position on the circle)
on 02024-06-14#History of #BSP-tree #algorithms before #Doom. #games
on 02024-06-10#biography and obituary of Andrey Astrelin, who discovered the GrailSort #sorting algorithm before dying of glioblastoma multiforme at 47 in 02017. #algorithms
on 02024-06-10#video on #sorting #algorithms with colors #formina
on 02024-06-10#video of #algorithms for pathfinding, such as A*, etc.
on 02024-05-29#video of 80 #sorting #algorithms with music, including lots I hadn’t heard of: Andreysort (Grailsort), bitonic sort, odd-even sort, circle sort, cycle sort, weak heap sort, etc. It’s always sorting the numbers 0 to N (either N=8, N=16, N=32, N=64, N=128, N=1024, or N=2048) and emits two tones whose frequencies are determined by the two numbers being considered.
on 02024-05-26#raytracing #graphics including #algorithms like resampled importance sampling, reservoir sampling, temporal reuse, spatial reuse, and #ReSTIR. Another very nice pure-CGI #video
on 02024-05-18David Greenberg’s "Hitchhiker Tree" data structure #algorithms #video
on 02024-04-05#Bresenham #graphics #algorithms modified to draw thick lines
on 02024-02-21#PDF #paper from #Bresenham in 01965 giving Bresenham’s line-drawing algorithm: “Algorithm for computer control of a digital plotter”. Says the original paper was “An incremental algorithm for digital plotting” in 01963. Also incidentally says Iverson “introduced” the floor/ceiling notation, though as they were both IBMers, possibly we should take that “seriously but not literally”. 2-D #graphics #algorithms
on 02024-01-28#Audio playback and recording with a PIC or other small microcontroller #hardware from a 1-bit (?) bitstream, using the standard RC time constant model (but with the time constant scaled to be a factor of 2 instead of e) in different #algorithms. He scales the waveform down to half the maximum possible amplitude and then models the RC time constant with each possible bit, with the sample time set to a decay factor of ⅛ (which I guess is .133τ) to see which one gives a smaller error, and goes with that bit. He got acceptable response at 19.5ksps.
on 02024-01-232-D #graphics #algorithms for simplifying Bézier paths, describing an algorithm implemented in his Rust library for 2-D shapes, "kurbo".
on 02024-01-142-D #graphics #algorithms for outlining Bézier strokes. “This post presents a significantly better solution to the parallel curve problem than the current state of the art.” Includes #explorable-explanations.
on 02024-01-14the #Slug 2-D #graphics #algorithms #paper, “GPU-Centered #Font Rendering Directly from Glyph Outlines”, by Lengyel, #CC BY-ND, 02017
on 02024-01-14#PCG32 #PRNG #paper #PDF showing 29-66 gigabits per second #performance, more than twice the Mersenne Twister and ten times Arc4random. Same author as the “Genuine Sieve of Eratosthenes” #algorithms paper.
on 02023-12-06a #small-is-beautiful non-cryptographic #PRNG called "PCG32" by M.E. O'Neill, in 9 lines of #C. #algorithms
on 02023-12-06Chris #Wellons explains hash #trie #algorithms in C, recommending a 4-way branching factor with arena allocation. Not the same as #HAMT. #performance
on 02023-12-06nice #PDF slide deck about histogram filters, similar to #particle-filters, with Octave code to implement it. #algorithms #machine-learning
on 02023-10-07#algorithms using uninitialized memory for constant-time #performance for sparse integer sets (citing Briggs and Torczon’s 01993 paper)
on 02023-10-07#performance of #quicksort on current hardware improves with, among other things, branchless bubble #sorting #algorithms instead of insertion sort, which is damned surprising
on 02023-09-25some #ebooks about #algorithms and stuff
on 02023-09-19#pointcloud #3D #graphics #algorithms with a tiny #ASCII-art implementation in a few lines of C. #small-is-beautiful
on 02023-09-19interesting fast approximate #matrix-multiply #algorithms using sorting, first differences, and logarithm LUTs?
on 02023-07-07#PDF #paper by David Gries “Schorr-Waite Graph Marking Algorithm –Developed With Style” where he gives the Deutsch-Schorr-Waite #garbage-collection graph-marking algorithm as something like p = root; q = vroot; while (p != vroot) { p.m++; if (p.m == 3 || p.car.m == 0) { [p, p.car, p.cdr, q] = [p.car, p.cdr, q, p]; } else { [p.car, p.cdr, q] = [p.cdr, q, p.car]; } where the comma-assignment statements are multiple assignments and .m goes from 0 (for unvisited) to 3 (for marked), nil pointers are represented by pointers to a node whose car and cdr point to itself, and vroot is a special distinguished node that we pretend is the parent of the root. #algorithms
“Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering, by Michael A. Bender, Bradley C. Kuszmaul, and William Kuszmaul” #PDF #paper on #hashing #algorithms #performance with "graveyard hashing"
on 02023-07-03ICA #algorithms separate an additive mixture into independent non-Gaussian signals; nsh suggests you could use this to separate a font into additive components.
on 02023-02-01new sieve of Eratosthenes #algorithms with O(N^{1/3} (log N)^{2/3}) space and O(N log N) time #performance
on 02023-01-15#zstd #compression #algorithms and file format
on 02022-09-16the confusing parts of the #gzip and #deflate #compression #algorithms
on 02022-09-16#gzip #compression #algorithms and file format in depth
on 02022-09-16#Raph Levien’s treatise on #algorithms with #ropes and their #performance in his #editor Xi
on 02022-09-16#FFT #algorithms #performance with blocking and cache-oblivious approaches
on 02022-09-16Bresenham’s #graphics #algorithms for lines, circles, axis-aligned #ellipses, and Bézier curves.
on 02022-05-27“The High Precision DDA for Ellipse-Generation”, by Hong Tao, Aircraft Manufacturing Engineering Dept., Northwestern Polytechnical University, Xi’an, The People’s Republic of China, #graphics #algorithms for #ellipses from 01988
on 02022-05-27munificent’s page on his roguelike dungeon #mapgen #algorithms, with #explorable-explanations. He first places random non-overlapping (rectangular) rooms, generates a #maze to fill the rest of the space, connects the rooms and mazes to form a spanning tree (plus a few extra connections), and then removes the dead ends as per Jamis Buck (as with Basem Nayfeh’s #cellular-automata approach). Nice animations with pastel colors and relief shading.
on 02022-05-21A Adonaac’s page on TinyKeepDev’s dungeon #mapgen #algorithms, with animations and #Lua code
on 02022-05-21Eli Bendersky’s article on Pratt’s #top-down-operator-precedence #parsing algorithm, using as an example infix arithmetic with parentheses in Python. #algorithms
on 02021-01-21Fredrik Lundh’s explanation of Pratt’s #top-down-operator-precedence #parsing algorithm in Python. #algorithms
on 02021-01-21Crockford’s explanation of the Pratt #top-down-operator-precedence #parsing algorithm; Crockford presents a #JS parser that can parse the JS subset it’s written in, cut down from his JSlint. #algorithms #smallisbeautiful
on 02021-01-21Another inspiring #incremental #PEG #parsing sketch by Darius Bacon. #algorithms
on 02021-01-15#BDD #algorithms, "The Language of Choice"
on 02021-01-13discussion of #graphics #dithering #algorithms including output-dependent feedback
on 02021-01-13a fairly comprehensive summary of #graphics #dithering #algorithms
on 02021-01-13the good-looking textured light-sourced bouncy fun smart and stretchy page, on #graphics #algorithms
on 02021-01-132002 #PDF #paper by Markus Kuhn on "Optical TEMPEST", recovering image data from time-domain fluctuation in light from a CRT. Includes #algorithms for clock and data recovery, surprisingly! (He was thinking maybe you could snoop data from modem LEDs.) Very nicely presented, too.
on 02020-12-24Bresenham’s #algorithms for plotting lines, ellipses, antialiased quadratic Bézier curves, etc. #graphics
on 02020-12-01#algorithms for rotating raster #graphics (with three shears)
on 02020-12-01where Rasmus confesses that in 1994 PHP used strlen() as its hash function for function names :) #hashing #algorithms
on 02020-10-10#fractals #algorithms #3D #rendering
on 02018-10-05#PDF on #FFT #algorithms on Intel GPUs, including some architectural details: each EU has 7 hardware threads, each with 128 32-byte registers, 512 bytes per work item in SIMD-8 mode, but only 2 32-bit #floating-point ALUs #GPGPU
on 02018-10-05#PDF #paper on different #algorithms that are all kind of the same “multiplicative weights update method”
on 02018-08-16Different important #algorithms that are Dijkstra’s shortest-path graph traversal algorithm on a number of other kinds of graphs.
on 02018-08-16#3D terrain rendering #algorithms from Novalogic’s 01992 game “Comanche” in 20 lines of #graphics code, using ray-casting in voxel space (?) — a pretty standard #heightfields rendering thing really #smallisbeautiful #voxelspace
on 02017-11-25#Graphics #performance #algorithms: running console graphics pipeline #emulation (of the Nintendo GameCube, specifically, in the Dolphin emulator) in a pseudo-GPGPU "Ubershader"
on 02017-07-30how to test #algorithms for #persistent-memory without actually physically having any, from a blog on persistent-memory programming
on 02017-07-13The SciPy #Python #library comes with a whole passel of #optimization #algorithms.
on 02017-07-13The BK-tree, or Burkhard-Keller tree, from Damn Cool #Algorithms. It’s a kind of index that gives you fast approximate string matching, so you can e.g. find misspelling candidates from a dictionary.
on 02017-07-11discussion thread on #origami #algorithms
on 02017-07-01#PDF of a Henry Baker #paper about complex #math #algorithms and CORDIC and whatnot. #geometry #graphics
on 02017-05-27#algorithms for #concurrency: mutual exclusion without compare-and-swap or test-and-set primitives, just atomic variable reads and writes.
on 02017-05-20#paper on #algorithms for #compressed-indexing in deterministic linear time. “We show that the compressed suffix array and the compressed suffix tree of a string T can be built in O(n) deterministic time using O(nlogσ) bits of space, where n is the string length and σ is the alphabet size.”
on 02017-05-19Björn’s table-driven UTF-8 decoder in 10 lines of C, not counting the 384-byte table. #Unicode #algorithms #smallisbeautiful
on 02017-04-26Jon Blow is cynical about #algorithms like the ones used in Raph #Levien’s editor #xi.
on 02017-04-26Hmm, a Dyck language and a regular language intersected give you an arbitrary context-free language? #parsing #algorithms
on 02017-04-26#Algorithms in Python, with Jupyter notebooks for practicing programming them in. “Challenges focus on algorithms and data structures found in coding interviews.”
on 02017-04-18Golomb-compressed sets (GCSes) provide similar functionality to #Bloom-filters but are smaller. “While a compressed Bloom filter treats this as a bitmap, a GCS treats it as a list of values. Since the values are the result of hashing, we can assume that they are uniformly distributed, sort them and build a list of differences. The differences will be geometrically distributed with a parameter of p. Golomb coding is the optimal encoding for geometrically distributed values: you divide by 1/p, encode that in unary then encode the remainder in binary.” #algorithms
on 02017-04-15AA trees are a simplified variant of the red-black tree data structure #algorithms where red links are only on the right child, thus implementing a 2-3 tree instead of a 2-3-4 tree; less space-efficient, because each node requires a level number.
on 02017-03-22#FFT #algorithms for #DSP expressed or explained in BASIC. #smallisbeautiful
on 02017-03-22BSD-licensed diff algorithm in Python by sbp and Tony Garnock-Jones, using the Ukkonen-Myers algorithm. Diff and patch are 64 lines of code, including blanks. #smallisbeautiful #algorithms
on 02017-03-22Skip list #algorithms #performance
on 02017-03-11#math #paper #PDF on “unbounded spigot #algorithms” for digits of π
on 02017-03-11Explanation of the ChaCha20 #crypto algorithm. #algorithms #toread
on 02017-01-10Malte Skarupke describes his ska_sort, a radix #sorting algorithm that beats the comparison-based implementation in (some implementation of) the STL on modern hardware by a factor of two to seven, largely due to better instruction-level parallelism. Typically it starts to win at about 64 items. #algorithms
on 02017-01-03efficient skip list #algorithms, with nice diagrams made with Dia and TikZ
on 02016-12-21Ken Perlin’s simplex-noise software patent. :( #graphics #algorithms #patents
on 02016-11-21Ken Perlin won an Oscar for the Perlin noise, which he invented for Tron and later improved with “simplex noise”, which I think goes off-patent in 2022. #graphics #algorithms
on 02016-11-21a cuckoo filter is like that signed hash thing from Managing Gigabytes that is like a Bloom filter with deletion, and is often more space-efficient. #algorithms #paper #PDF
on 02016-10-11discussion of texture synthesis #algorithms including mxgmn’s new "wavefunction collapse" algorithm
on 02016-10-11Generating faces with deconvolution #neural-networks, supporting fairly realistic face interpolation. Lots of fun pictures from different kinds of #optimization #algorithms.
on 02016-10-03#graphics #algorithms #performance #sse #toread by #ryg
on 02016-09-29#graphics #algorithms rasterizing triangles with #barycentric coordinates without worrying about performance #toread by #ryg
on 02016-09-29improving #graphics #algorithms #performance with #barycentric coordinates. #toread by #ryg
on 02016-09-29“an algorithm and associated sample code [using #SSE] for software occlusion culling which is available for download” #algorithms #performance #toread this is what ryg was commenting on in his 2013 #graphics thread
on 02016-09-29Write combining can cause #performance problems in #graphics #algorithms or can speed them up. #toread by #ryg
on 02016-09-29#compression #algorithms #performance testing for end-of-buffer with branchless I/O etc. by #ryg
on 02016-09-29#interval-arithmetic #math #algorithms in ℤ/Nℤ #toread by #ryg
on 02016-09-29#compression codec #algorithms using #ryg’s rANS: Oodle LZNA and BitKnit #toread
on 02016-09-29#PDF #paper on “regular string transformations”, with #algorithms to evaluate them in linear time and cover much of the space of the standard regexp-replace-with-backreferences approach to string transformations.
on 02016-09-20A #Rust implementation of the #Cassowary #constraint solving algorithm, one of the linear-time #algorithms for constraint layout.
on 02016-08-03Bélády’s anomaly, discovered in 1969, is that FIFO paging #algorithms can produce more unboundedly page faults if given more page frames, screwing up #performance.
on 02016-08-03The Aggregate Magic #Algorithms, for things like popcount, int lg, logarithmic-time Gray code conversion, stuff like that.
on 02016-07-24An optimized integer division library, using multiplication and bitshifts, in part because the #SSE #ISA has no division instruction (like the Cray vector operations before it). #algorithms
on 02016-07-21something about the Winograd algorithm for doing convolution for convolutional #neural-networks. #algorithms
on 02016-07-04The Martelli and Montanari unification algorithm, which seems to be the one of the various unification #algorithms that everyone uses for #logic. This original #paper #pdf is 25 pages and clearer than most of the attempts at exegesis that I’ve seen.
on 02016-05-09“An overview of #gradient-descent #optimization #algorithms” “This blog post aims at providing you with intuitions towards the behaviour of different algorithms for optimizing gradient descent that will help you put them to use”
on 02016-05-04Computational #origami #geometry #algorithms on OpenCourseWare.
on 02016-03-29#pdf #paper describing the Viola-Jones #computer-vision #algorithms for rapid object detection combining a number of simple Haar-like features and AdaBoost, using sum tables (aka #prefix-sum or summed-area tables: “We choose a different name here in order to emphasize its use for the analysis of images, rather than for texture mapping.”)
on 02016-01-18“Making faces with Haar cascades and mixed integer linear programming”, a simple algorithm that generates faces based on the Viola-Jones #computer-vision object detection algorithm, by using a “mixed integer linear programming” #constraint solver. #algorithms
on 02016-01-18Quick #pdf #introduction to #gradient-descent #optimization #algorithms.
on 02016-01-13“local search” is the family of #optimization #algorithms that includes hill climbing, gradient descent, simulated annealing, and tabu search.
on 02016-01-13#paper #pdf #introduction to the SLAM (“simultaneous localization and mapping”) #robotics problem and the #algorithms for solving it, focusing on extended #Kalman-filters using a range measurement device. SLAM is the process of building some sort of model of the world your robot is in while also figuring out where you the robot is in that world. Unfortunately, this overview is from 2005, more than ten years old now, before the particle-filter revolution.
on 02016-01-11#automatic-differentiation of symbolic expressions provides #algorithms for linear-time rather than quadratic-time symbolic differentiation
on 02016-01-08“SPHINCS-256 is a high-security #post-quantum stateless hash-based signature scheme that signs hundreds of messages per second on a modern 4-core 3.5GHz Intel CPU. Signatures are 41 KB, public keys are 1 KB, and private keys are 1 KB. SPHINCS-256 is designed to provide long-term 2128 security even against attackers equipped with quantum computers.” #djb #crypto #algorithms
on 02016-01-06#Alexandrescu invented new #algorithms for O(√n) searching and sorting based on a quadratically-growing collection of max-heaps in order to get better locality of reference. Also, shockingly, he hadn’t heard of cache-oblivious data structures until now!
on 02015-11-30explains why standard edge-detection #algorithms are as good as John Costella’s. #computer-vision
on 02015-11-22John Costella claims his edge detection algorithm for #computer-vision is better than standard #algorithms, using a bilinear upsampling kernel.
on 02015-11-22an 8-page 2011 #pdf #paper by Pedamallu, Kumar, Csendes, and Posfai on continuous #constraint satisfaction by tree search by interval subdivision, aka interval partitioning (to which they give the deeply unfortunate acronym “IP”), compared with three other interval methods. Doesn’t mention Hyvonen. Recursively partitions hyperdimensional boxes along many dimensions at once, creating 2ⁿ new boxes, and uses “new dynamic stage-wise tree search" #algorithms which I don’t understand to figure out which box to partition next. Applications given to #kinematics, on which it unfortunately wastes a precious page and a half; their last stage is to pass off the feasible boxes found to a Feasible Sequential Quadratic Programming algorithm for I guess optimization or something?
on 02015-11-18A 2010 explanation of the "finger tree" data structure and the #algorithms on it, with Edward Kmett in the comments.
on 02015-11-16interesting, a representation for rational numbers with simple and efficient #algorithms, including for division.
on 02015-11-16#algorithms for Okasaki’s #FP-persistent red-black #trees: specifically how to delete nodes.
on 02015-11-16the interval tree data structure and #algorithms. #trees
on 02015-11-16#van-Emden opines about the “algorithmic paradigm” that is sort of supplanting the “formulaic paradigm”. Very thought-provoking, and kind of parallel to some of the stuff Alan Kay is working on at #CDG. #calendar #algorithms
on 02015-10-29Binary-search #algorithms results that shows how using an implicit binary search tree packed into an array can roughly double your binary-search speed over merely sorting, due to cache effects. #trees
on 02015-10-19Tony Finch’s trie based on #DJB’s crit-bit #trees but consuming less memory by branching on nibbles, with a 16-bit sparsity bitmap. #algorithms
on 02015-10-04an adaptive radix tree (#trie) “ART” in C99 #algorithms #trees
on 02015-10-04this "Stratified B-trees" paper presents “a fully-versioned B-tree with optimal space and the same lookup time as the [copy-on-write] B-tree”, and also supports fully-versioned updates in o(1) IOs in linear space, by merging sorted arrays of (key, version, value) tuples, followed by “density amplification” by de-merging the arrays if they are not dense enough (<⅓) in some of the versions. Nodes are immutable once written. May also be relevant to Cuerda. #algorithms #trees
on 02015-09-09A new wiki about #algorithms.
on 02015-09-01Satan explains #suffix-array construction #algorithms, focusing on the SA-IS linear-time algorithm.
on 02015-08-23#paper on the “consistent overhead byte stuffing” #encoding algorithm ("COBS"), which encodes your packets to avoid an illegal byte value adding no more than 0.4% space overhead in the worst case. If the illegal value is NUL, it works by transforming a packet that is a sequence of NUL-terminated strings into a sequence of length-byte-preceded strings, with an excess-1 encoding for the length; strings of over 254 bytes are encoded by a concatenation of 255-byte chunks counted with 0xFF, followed by a regular counted chunk. #algorithms
on 02015-08-20A survey #paper of #parallel #prefix-sum #algorithms, finding that the Kogge-Stone algorithm is more common in #GPGPU code than Blelloch’s, and with handy diagrams so you can see what they’re talking about! Also they apparently wrote a thing to use #formal-methods to verify different implementations.
on 02015-08-15The Ladner & Fischer 1980 #paper on #parallel #algorithms for #finite-automata using #prefix-sum, with its unnecessary extra N² inefficiency compared to the N lg N in Hillis & Steele 1986. I think, anyway. I haven’t really read the paper.
on 02015-08-15#Algorithms for best #performance on a #parallel #prefix-sum in #CUDA for #GPGPU as of 2007.
on 02015-08-15Rain World: a 2012 2D platformer indie #video-games prototype with a slugcat protagonist, procedurally generated animations, and filtered collages for level backgrounds. Includes some tips on #A* #search #algorithms in tricky situations.
on 02015-08-15“Prefix Sums and Their Applications”, Blelloch 93. This is the definitive #paper on #prefix-sum #algorithms as of uh 22 years ago. It mentions specifically a #regular-expression #search-engine and #lexing as two of the applications of prefix sum! I think the “parallel solution of recurrence problems” mentioned here can be applied to #DSP IIR filtering. This is just “Chapter 1” (of what, I have no idea), but it promises more meat in chapters 2, 3, and 4, mostly to do with linked lists and trees.
on 02015-08-15The homepage of the Porter Stemmer #NLP stemming algorithm, among the most-widely-used stemming #algorithms, with dozens of implementations. Recommends using the Snowball stemmer instead, except for “IR research work involving stemming where the experiments need to be exactly repeatable”.
on 02015-08-15“#Levenshtein automata can be simple and fast” and useful for finding potential misspellings (like for a #search-engine, with applications given to #Lucene) in a #trie. #Python with #graphviz: 40 lines of code and good (O(max edit distance) supposedly) worst-case #complexity. #smallisbeautiful #algorithms
on 02015-08-15Code for several standard #algorithms for the multi-armed #bandit problem, in #Python, #Julia, and #Ruby.
on 02015-08-13This #tutorial #introduction to A* #pathfinding #search for #video-games programming, by @redblobgames, has interactive demonstrations! I don’t remember those from before! The #UX somewhat lacks affordances to indicate that the things in the illustrations are draggable, so the text has to tell you, but in many other ways, these are among the best #visualization of #algorithms I’ve ever seen.
on 02015-08-13The 2012 #trading #algorithms #paper about convex optimization.
on 02015-08-13Another #trading #algorithms #paper by the same authors as the 2011 paper: “Efficient market making via convex optimization, and a connection to online learning (2012)”. Talks about Arrow-Debreu #prediction-markets as a market-based probability estimator and draws a connection to online #machine-learning algorithms, and briefly links to computational #complexity results. The reason the authors are interested in automated market-making seems to be that it is needed to make #prediction markets over complex outcome spaces feasibly liquid.
on 02015-08-13A #paper about #trading: “An Optimization-Based Framework for Automated Market-Making (2011)”, reducing market-making to convex #optimization, and by relaxing the convex hull you can get the #algorithms to be computationally tractable without sucking too badly.
on 02015-08-13Oh my, the #OCaml Batteries Included package includes #algorithms and data structures like finger trees, dynamic arrays, abstract iteration (“enumeration”), UTF-8, and serialization (“marshal”). No inotify though.
on 02015-08-13Online #algorithms in high-frequency #trading (2013). This might be helpful in figuring out what kinds of things HFT algorithms can’t do in small or bounded memory, and therefore what exploitable market inefficiencies might still exist at the subsecond timescale.
on 02015-08-13The #RMQ #algorithms analogue for finding the modal element of a given range.
on 02015-08-10Another #RMQ #algorithms #tutorial, this one in #C++.
on 02015-08-10#RMQ via LCA #tutorial. #algorithms
on 02015-08-10Generalizations of #RMQ to arbitrary semigroups and other things, including range mode query and range median query. #algorithms
on 02015-08-10apparently an implementation of #RMQ via LCA? #algorithms
on 02015-08-10different #RMQ #algorithms, including RMQ via least common ancestor (LCA)
on 02015-08-10#RMQ #algorithms I didn’t know about.
on 02015-08-10Among #RMQ #algorithms there’s a special case that’s linear-time when the range in question is a sliding window.
on 02015-08-10#algorithms seems like a programming-contest Wiki under cc-by?
on 02015-08-10Hmm, I hadn’t heard of this “binary indexed tree” or “Fenwick tree” alternative to the segment tree (#algorithms) that can’t handle #RMQ problems, in half the space and less time. It sounds like #mipmapping of #sumtables?
on 02015-08-10#python #algorithms not in the standard library.
on 02015-08-10“a logarithmic-time alternative to summed-area tables for reducing arbitrary semigroup operations over arbitrary ranges (a generalization of #RMQ segment trees)” #cumsum #algorithms #sumtables
on 02015-08-10Meredith’s tie-tying knot enumeration #algorithms
on 02015-08-05#subsetsum #algorithms in O(u √n) for set of size n computing subset for all target numbers t≤u #complexity
on 02015-08-05