**mechazoidal + algorithms**
139

Jones on modulus without division

17 days ago by mechazoidal

Useful on resource-constrained hardware that has no/slow division functions

math
embedded
algorithms
programming
17 days ago by mechazoidal

patience diffing algorithm

24 days ago by mechazoidal

tedu: "I needed a (text) diff algorithm, and if you search for one you mostly come up with the Myers algorithm. But then I stumbled across something called patience diffing, and it turns out to be just what I wanted. It’s already described elsewhere, but it seems more people could stand to know about it, so here we are. It’s easy to understand, and more importantly, usually makes pretty diffs (often prettier than Myers). "

algorithms
diff
dvcs
24 days ago by mechazoidal

GitHub - bloc97/Anime4K: A High-Quality Real Time Anime Upscaler

4 weeks ago by mechazoidal

"High-quality real-time anime upscaling SISR algorithm that can be implemented in any programming language, anywhere."

"Remarkably, the proposed method does not use any machine-learning or statistical approach, and is tailored to content that puts importance to well defined lines/edges while tolerates a sacrifice of the finer textures. The proposed algorithm can be quickly described as an iterative algorithm that treats color information as a heightmap and 'pushes' pixels towards probable edges using gradient-ascent. This is very likely what learning-based approaches are already doing under the hood (eg. VDSR, waifu2x)."

As of 2019 the example implementations are using HLSL(MPC-BE with madVR)

algorithms
graphics
anime
piperesearch
repo:github
"Remarkably, the proposed method does not use any machine-learning or statistical approach, and is tailored to content that puts importance to well defined lines/edges while tolerates a sacrifice of the finer textures. The proposed algorithm can be quickly described as an iterative algorithm that treats color information as a heightmap and 'pushes' pixels towards probable edges using gradient-ascent. This is very likely what learning-based approaches are already doing under the hood (eg. VDSR, waifu2x)."

As of 2019 the example implementations are using HLSL(MPC-BE with madVR)

4 weeks ago by mechazoidal

Unity 2D Line Segment Intersection · GitHub

june 2019 by mechazoidal

@stevestreeting: I couldn't find a core 2D line segment intersection routine in Unity and I didn't really like the forum solutions, so I wrote my own, it's here in case anyone else wants it:

unity3d
gamedev
algorithms
gist
june 2019 by mechazoidal

a flexible data structure for geometries - Game Development Stack Exchange

may 2019 by mechazoidal

"geometric representation are usually chosen based on two basic factors": topological and algorithmic

piperesearch
datastructures
stackoverflow
algorithms
may 2019 by mechazoidal

Towards a text editor construction kit · Issue #1187 · xi-editor/xi-editor · GitHub

may 2019 by mechazoidal

"Thoughts on why CRDT didn't work out as well for collaborative editing xi-editor"

Biggest problems: handling IME, trying to have the CRDT do everything, there are still some unknowns. Note that most of these are about text editing.

crdt
algorithms
collaboration
comment
xi_editor
2019
piperesearch
Biggest problems: handling IME, trying to have the CRDT do everything, there are still some unknowns. Note that most of these are about text editing.

may 2019 by mechazoidal

Laurence Tratt: Parsing: The Solved Problem That Isn't

april 2019 by mechazoidal

"This article is my attempt to write down my current understanding and, in particular, the limitations of current approaches when composing grammars; I welcome corrections from those more knowledgeable than myself. Predicting the future is a mugs game, but I am starting to wonder whether, if we fail to come up with more suitable parsing algorithms, programming languages of the future that wish to allow syntax extension will bypass parsing altogether, and use syntax directed editing instead. Many people think parsing is a solved problem - I think it isn't."

parser
computerscience
programming
algorithms
parsing
april 2019 by mechazoidal

message threading

april 2019 by mechazoidal

jwz explains the One True Email Threading algorithm, and why it's such a pain in email

email
algorithms
reference
rfc822
april 2019 by mechazoidal

research!rsc: Transparent Logs for Skeptical Clients

march 2019 by mechazoidal

"The Certificate Transparency project publishes TLS certificates in this kind of log. Google Chrome uses property (1) to verify that an enhanced validation certificate is recorded in a known log before accepting the certificate. Property (2) ensures that an accepted certificate cannot later disappear from the log undetected. Property (3) allows an auditor to scan the entire certificate log at any later time to detect misissued or stolen certificates. All this happens without blindly trusting that the log itself is operating correctly. Instead, the clients of the log—Chrome and any auditors—verify correct operation of the log as part of accessing it."

cryptography
algorithms
security
datastructures
march 2019 by mechazoidal

Modern LZ Compression

february 2019 by mechazoidal

"By the end, we will have a compressor that can beat gzip while decompressing at almost the same speed — in less than 1000 lines. You can find the source for the article at https://github.com/glinscott/linzip2 "

compression
algorithms
programming
reference
february 2019 by mechazoidal

Algorithms by Jeff Erickson

january 2019 by mechazoidal

"This web page contains a free electronic version of my (soon to be) self-published textbook Algorithms, along with other lecture notes I have written for various theoretical computer science classes at the University of Illinois, Urbana-Champaign since 1998."

(CS374, CS473)

algorithms
programming
computerscience
reference
book
ebook
(CS374, CS473)

january 2019 by mechazoidal

better geometry through graph theory

september 2018 by mechazoidal

"A few months ago, I decided to implement set operations on curved regions. I had the the canonical textbook on computational geometry, which described approaches for polygons comprised of straight lines, and it seemed like other projects had extended these techniques to parametric curves. I figured it would take a couple of weeks.

Unfortunately, the field of computational geometry embodies a fundamental contradiction. In geometry, the angles of a triangle add up to exactly π radians, and if u is clockwise from v then v must be counter-clockwise from u. Computers, on the other hand, use floating point representations which make a mockery of these simple Euclidean truths."

Note his solution based on error-correcting codes, and the Java implementation.

Also, these examples are for 2d polygon clipping, not sure if it can be extended into 3d.

math
geometry
graph
graphics
algorithms
piperesearch
2d
Unfortunately, the field of computational geometry embodies a fundamental contradiction. In geometry, the angles of a triangle add up to exactly π radians, and if u is clockwise from v then v must be counter-clockwise from u. Computers, on the other hand, use floating point representations which make a mockery of these simple Euclidean truths."

Note his solution based on error-correcting codes, and the Java implementation.

Also, these examples are for 2d polygon clipping, not sure if it can be extended into 3d.

september 2018 by mechazoidal

Eric Jang: Dijkstra's in Disguise

august 2018 by mechazoidal

"We have 3 very well-known algorithms (currency arbitrage, Q-learning, path tracing) that independently discovered the principle of relaxation used in shortest-path algorithms such as Dijkstra's and Bellman-Ford. Remarkably, each of these disparate fields of study discovered notions of hard and soft optimality, which is relevant in the presence of noise or high-dimensional path integrals."

It's shown how it applies to finance and computer graphics.

algorithms
graph
rendering
math
finance
It's shown how it applies to finance and computer graphics.

august 2018 by mechazoidal

Aho–Corasick string search | Lobsters

july 2018 by mechazoidal

burntsushi covers WHY AC is so good, including potential pitfalls. Another comment has link to original paper.

lobsters
comment
algorithms
strings
july 2018 by mechazoidal

countercomplex: Some deep analysis of one-line music programs.

july 2018 by mechazoidal

Follow-up to the original, contains a lot of music theory

music
audio
programming
bytebeat
algorithms
reference
july 2018 by mechazoidal

The blog at the bottom of the sea « Programming, Graphics, Gamedev, Exotic Computation, Audio Synthesis

april 2018 by mechazoidal

"Programming, Graphics, Gamedev, Exotic Computation, Audio Synthesis"

PR: check out Skeletal Animation

algorithms
programming
gamedev
piperesearch
demoscene
PR: check out Skeletal Animation

april 2018 by mechazoidal

Holding algorithms (and the people behind them) accountable is still tricky, but doable | Nieman Journalism Lab

march 2018 by mechazoidal

"[Nick Diakopoulos] advised interested journalists to be aware of missing information when governments are reluctant to share, to have an expectation of what an algorithm is supposed to do, and to know that it’s never one-and-done since algorithms can always be tweaked. And remember, it’s usually humans that are doing the tweaking. “As reporters, we really need to push to hold people accountable. Don’t let corporations say ‘it was the algorithm,'” Diakopoulos said. “You need to push on that more and find out where the people are in this system.”

journalism
algorithms
investigation
march 2018 by mechazoidal

Doing the FizzleFade effect using a Feistel network

august 2017 by mechazoidal

"doing this with a pseudo random generator, as noted in the blog post, is slow, but is also visually very unpleasant, since the more red pixels you have on the screen already, the less likely is that you hit a new yet-not-red pixel, so the final pixels take forever to turn red. [...] While not rocket science, it was possibly hard for other resolutions to find a suitable LFSR. However regardless of the real complexity of finding an appropriate LFSR for other resolutions, the authors of the port could use another technique, called a Feistel Network, to get exactly the same result in a trivial way."

math
programming
graphics
algorithms
august 2017 by mechazoidal

Fizzlefade

august 2017 by mechazoidal

The "death" screen in Wolf3d is done via a LFSR implemented in 16-bit Intel assembly.

(Although see http://antirez.com/news/113 for a version using a Feistel network)

programming
algorithms
gamedev
assembly
(Although see http://antirez.com/news/113 for a version using a Feistel network)

august 2017 by mechazoidal

SymSpell vs. BK-tree: 100x faster fuzzy string search & spell checking

july 2017 by mechazoidal

"Use SymSpell, if speed is important. It is 2–3 orders of magnitude faster than BK-Tree and 5–6 orders of magnitude faster than Norvig’s algorithm. Use LinSpell, if memory usage is important. It is 10* faster than BK-Tree for same memory usage."

(there are no advantages in a BK-tree or Norvig's algorithm, for practical purposes)

algorithms
spelling
programming
reference
from:medium
text
(there are no advantages in a BK-tree or Norvig's algorithm, for practical purposes)

july 2017 by mechazoidal

Miniball - Mike Bostock - d3.express

june 2017 by mechazoidal

Visualized walkthrough of the Matoušek-Sharir-Welzl algorithm, for making circles incorporating other circles

piperesearch
graphics
algorithms
d3
visualization
june 2017 by mechazoidal

How to Generate Random Colors Programmatically | lobste.rs

may 2017 by mechazoidal

"I came in expecting the usual revelation about “Oh, RGB < HSL/HSV for this sort of work”, but the golden ratio bit was quite nifty. "

reference
discussion
lobsters
colors
design
algorithms
may 2017 by mechazoidal

Spelling with Elemental Symbols

may 2017 by mechazoidal

"Finally, it feels good to have answered my own initial question. I know longer have to wonder about elemental spellings because I now have a tool to find them for me, and with a quick pip install stoichiograph, you can too."

python
algorithms
optimization
programming
datastructures
may 2017 by mechazoidal

Introduction to Video Coding

march 2017 by mechazoidal

Big PDF presentation on video encoding/decoding: Huffman, DCT, YUV, oh my!

video_editing
pdf
slides
math
algorithms
reference
march 2017 by mechazoidal

smalLZ4 - optimal LZ4 compression

february 2017 by mechazoidal

An optimized LZ4 compressor, with code and a walkthrough of LZ4 compression.

compression
algorithms
programming
february 2017 by mechazoidal

xxHash: Extremely fast non-cryptographic hash algorithm

february 2017 by mechazoidal

"an Extremely fast Hash algorithm, running at RAM speed limits. It successfully completes the SMHasher test suite which evaluates collision, dispersion and randomness qualities of hash functions. Code is highly portable, and hashes are identical on all platforms (little / big endian)." A list of language-specific libraries implementing it is provided.

hash
library
programming
algorithms
compression
february 2017 by mechazoidal

Open source IMU and AHRS algorithms | x-io Technologies

february 2017 by mechazoidal

"In 2009 Sebastian Madgwick developed an IMU and AHRS sensor fusion algorithm as part of his Ph.D research at the University of Bristol. The algorithm was posted on Google Code with IMU, AHRS and camera stabilisation application demo videos on YouTube. The algorithm received thousands of downloads but the code project was never maintained or updated. All resources are now provided and maintained here. The algorithm source code is available in C, C# and MATLAB. The source code also includes Madgwick’s implementation of Robert Mayhony’s ‘DCM filter‘ in quaternion form."

motion_tracking
algorithms
ahrs
programming
sensors
february 2017 by mechazoidal

RC40 card cipher

february 2017 by mechazoidal

"Now that we have a [playing] card to represent each of our 5.32 bit bytes (I believe the PDP-7 used 5.32 bit bytes. Or was it the PDP-8?), we’re ready to execute the RC40 algorithm. It’s exactly the same as the RC4 algorithm, except every instance of 256 is replaced by 40. Simple, no?"

cryptography
algorithms
february 2017 by mechazoidal

Linear time suffix array construction

february 2017 by mechazoidal

A high-level description of the DC3 / "skew algorithm" for suffix array construction, running in linear time. A C++ version is provided at the end

algorithms
text
computerscience
pdf
february 2017 by mechazoidal

Distributed Algorithms (The Morgan Kaufmann Series in Data Management Systems)

november 2016 by mechazoidal

by Nancy Lynch. @mtnygard: "The underlying theorems still work. We have found new algorithms that aren’t in her book, of course. I found that the book was invaluable to understand those algorithms and their proofs."

book
amazon
distributed
algorithms
november 2016 by mechazoidal

Jeff Erickson's Algorithms, Etc.

november 2016 by mechazoidal

- Recursion

- Randomization

- Amortization

- Basic graph algos

- Combinatorial optimization

- Hardness

algorithms
reference
resource
computerscience
math
- Randomization

- Amortization

- Basic graph algos

- Combinatorial optimization

- Hardness

november 2016 by mechazoidal

mxgmn/WaveFunctionCollapse

september 2016 by mechazoidal

"Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics."

generator
gamedev
graphics
repo:github
algorithms
september 2016 by mechazoidal

Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy

september 2016 by mechazoidal

@brinker: "It’s a book about the ways in which algorithms (and, more broadly, math) are used to give a veneer of subjectivity and rightness to good old human bigotry, carelessness, and evil. [...] And that’s just the first 100 pages!"

book
big_data
algorithms
amazon
september 2016 by mechazoidal

The Treacherous Optimization

september 2016 by mechazoidal

"Old age and treachery will beat youth and skill every time."

"Put another way, grep sells out its worst case (lots of partial matches) to make the best case (few partial matches) go faster. How treacherous! As this realization dawns on me, the room seemed to grow dim and slip sideways."

grep
optimization
algorithms
search
post
"Put another way, grep sells out its worst case (lots of partial matches) to make the best case (few partial matches) go faster. How treacherous! As this realization dawns on me, the room seemed to grow dim and slip sideways."

september 2016 by mechazoidal

ferd.ca -> Simhashing (hopefully) made simple

august 2016 by mechazoidal

"While simhashes still aim to have unique signatures for documents, they also attempt to make sure that documents that look the same get very similar hashes. That way, you can look for similar hashes to figure out if the documents are closely related, without needing to compare them bit by bit. It's a statistical tool to help us find near-duplicates faster."

simhash
text
programming
hash
data_mining
algorithms
august 2016 by mechazoidal

The tessellate polygon algorithm

july 2016 by mechazoidal

this is meant for 'GBox', 'a cross-platform 2d graphic library in c language'? Regardless, this looks like it's for tessellating 2d polygons for display

2d
graphics
piperesearch
math
algorithms
july 2016 by mechazoidal

Porter Stemming Algorithm

june 2016 by mechazoidal

The original and canonical stemming algorithm

reference
text
text_processing
programming
algorithms
june 2016 by mechazoidal

countercomplex: Algorithmic symphonies from one line of code -- how and why?

june 2016 by mechazoidal

the original bytebeat post: "Maybe it's just about technological mismatch: to builders of digital musical circuits, things like LFSRs may have been more appealing than very wide sequential counters. In the early days of the microcomputer, there was already enough RAM available to hold some musical structure, so there was never a real urge to simulate it with simple logic. Or maybe it's about the problems of an avant-garde mindset: if you're someone who likes to experiment with random circuit configurations or strange bit-shifting formulas, you're likely someone who has learned to appreciate the glitch esthetics and never really wants to go far beyond that."

bytebeat
post
music
composing
audio
algorithms
june 2016 by mechazoidal

Iocaine Powder Explained

may 2016 by mechazoidal

"a heuristically designed compilation of [roshambo] strategies and meta-strategies [...] to predict what the opponent will do. Given a successful prediction, it is easy to defeat the opponent (if you know they will play rock, you play paper). However, straightforward prediction will often fail; the opponent may not be vulnerable to prediction, or worse, they might have anticipated your predictive logic and played accordingly."

gamedev
game_theory
programming
algorithms
may 2016 by mechazoidal

The Best Algorithm No One Knows About | Kerf blog

april 2016 by mechazoidal

"Here’s a program roughly 0% of programmers know how to write: generate a list of random tweets, without duplication. You may think you know how to do this, but you almost assuredly don’t."

(given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform)

@tedu points out this is Method D from a 1984 paper by Jeffrey Vitter.

random
programming
gamedev
algorithms
(given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform)

@tedu points out this is Method D from a 1984 paper by Jeffrey Vitter.

april 2016 by mechazoidal

ROSALIND | Problems | Locations

february 2016 by mechazoidal

Like Project Euler, but for biology instead of math

programming
python
algorithms
biology
puzzles
february 2016 by mechazoidal

$1 Recognizer

january 2016 by mechazoidal

- "a 2-D single-stroke recognizer designed for rapid prototyping of gesture-based user interfaces"

- "under 100 lines of code that you can quickly add to your application to give it gesture recognition capabilities."

- Code is provided in both JS and C#, but note that only $1 itself is JS--the other libraries are C#.

uw
gesture
ui
algorithms
pmz
javascript
c#
library
- "under 100 lines of code that you can quickly add to your application to give it gesture recognition capabilities."

- Code is provided in both JS and C#, but note that only $1 itself is JS--the other libraries are C#.

january 2016 by mechazoidal

angel14995 comments on Why GNU grep is fast

december 2015 by mechazoidal

A great example of the Boyer-Moore algorithm in action, w.r.t grep.

explanation
reddit
computerscience
comment
algorithms
december 2015 by mechazoidal

qp tries: smaller and faster than crit-bit tries - Tony Finch

october 2015 by mechazoidal

"some simple benchmarks say qp tries have about 1/3 less memory overhead and are about 30% faster than crit-bit tries.

"qp trie" is short for "quadbit popcount patricia trie"

programming
datastructures
algorithms
"qp trie" is short for "quadbit popcount patricia trie"

october 2015 by mechazoidal

What the Hero Sees: Field-of-View for Roguelikes

september 2015 by mechazoidal

Using octants and shadow-casting, in a semi-new algorithm(starting from Bresenham).

roguelike
gamedev
post
algorithms
september 2015 by mechazoidal

Flake: A Decentralized, K-Ordered Unique ID Generator in Erlang -- Boundary

august 2015 by mechazoidal

"two basic goals:

- Id generation at a node should not require coordination with other nodes.

- Ids should be roughly time-ordered when sorted lexicographically.

In other words they should be k-ordered. All that is required to construct such an id is a monotonically increasing clock and a location."

(does not require Erlang features, was simply their implementation)

https://github.com/boundary/flake

piperesearch
library
distributed
pmz
algorithms
- Id generation at a node should not require coordination with other nodes.

- Ids should be roughly time-ordered when sorted lexicographically.

In other words they should be k-ordered. All that is required to construct such an id is a monotonically increasing clock and a location."

(does not require Erlang features, was simply their implementation)

https://github.com/boundary/flake

august 2015 by mechazoidal

How does a relational database work - Coding Geek

august 2015 by mechazoidal

A nice article on how RDBMSs work: from the algorithms on up. Good for DB OR data-structure newbies, as it covers merge-sort and explains big-O notation along the way

databases
programming
algorithms
learning
computerscience
august 2015 by mechazoidal

Levenshtein automata can be simple and fast

june 2015 by mechazoidal

"Do Levenshtein automata need to be difficult? We have an implementation with great worst case complexity in less than 40 lines of code, so I think the answer is no. [...] That’s the real advantage of any Levenshtein automaton: we can avoid searching the entire index by intelligently pruning the search space."

post
text
programming
algorithms
june 2015 by mechazoidal

julesjacobs/levenshtein

june 2015 by mechazoidal

"A simple proof of concept levenshtein automaton in Python"

python
text
search
github
algorithms
june 2015 by mechazoidal

tobyschachman.com/sketches/minimumpolygon/

april 2015 by mechazoidal

Analytically showing how a simple math solution(vs. a complete analytic solution) can work for "just get something on the screen" when it comes to graphics. In this case, constructing a minimal convex polygon hull using an 80's Fortran minimization algorithm(from numeric.js).

math
algorithms
ui
piperesearch
graphics
javascript
april 2015 by mechazoidal

Red Blob Games

january 2015 by mechazoidal

"I’ve been curating game development articles since 1990. All of my articles are available for free, with no signup and no ads. The main audience is independent, student, and hobbyist game developers, but I’d like to cover other math and computer science topics in the future. [...] Accompanying code is open source, under either the MIT License or the Apache v2 License."

gamedev
resource
articles
programming
math
algorithms
piperesearch
january 2015 by mechazoidal

A 10-MINUTE DESCRIPTION OF HOW JUDY ARRAYS WORK AND WHY THEY ARE SO FAST

december 2014 by mechazoidal

Are Judy arrays patented?

algorithms
datastructures
december 2014 by mechazoidal

Topic modeling made just simple enough.

december 2014 by mechazoidal

"[...] a way of extrapolating backward from a collection of documents to infer the discourses (“topics”) that could have generated them. (The notion that documents are produced by discourses rather than authors is alien to common sense, but not alien to literary theory.)"

More aimed at explaining it to researchers or laypeople, as the computer-science proofs for this and LDA (Latent Dirichlet Allocation) are "brain-squashingly hard".

text
datamining
analysis
algorithms
More aimed at explaining it to researchers or laypeople, as the computer-science proofs for this and LDA (Latent Dirichlet Allocation) are "brain-squashingly hard".

december 2014 by mechazoidal

Markov Chains

july 2014 by mechazoidal

A neat JS-powered visualization of Markov basics.

markov
algorithms
visualization
interactive
math
july 2014 by mechazoidal

A GPU Approach to Path Finding « null program

june 2014 by mechazoidal

Cleverly using fragment shaders to implement maze-solving cellular automata

gpu
maze
pathfinding
algorithms
june 2014 by mechazoidal

**related tags**

Copy this bookmark: