mechazoidal + algorithms   139

 « earlier
Jones on modulus without division
Useful on resource-constrained hardware that has no/slow division functions
math  embedded  algorithms  programming
17 days ago by mechazoidal
patience diffing algorithm
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
"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
4 weeks ago by mechazoidal
Unity 2D Line Segment Intersection · GitHub
@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
"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
"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
may 2019 by mechazoidal
Laurence Tratt: Parsing: The Solved Problem That Isn't
"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
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
"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
"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
"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
january 2019 by mechazoidal
better geometry through graph theory
"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
september 2018 by mechazoidal
Eric Jang: Dijkstra's in Disguise
"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
august 2018 by mechazoidal
Aho–Corasick string search | Lobsters
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
The blog at the bottom of the sea « Programming, Graphics, Gamedev, Exotic Computation, Audio Synthesis
"Programming, Graphics, Gamedev, Exotic Computation, Audio Synthesis"
PR: check out Skeletal Animation
algorithms  programming  gamedev  piperesearch  demoscene
april 2018 by mechazoidal
Holding algorithms (and the people behind them) accountable is still tricky, but doable | Nieman Journalism Lab
"[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
"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
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
august 2017 by mechazoidal
SymSpell vs. BK-tree: 100x faster fuzzy string search & spell checking
"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
july 2017 by mechazoidal
Miniball - Mike Bostock - d3.express
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
"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
"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
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
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
"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
"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
"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
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)
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.
- Recursion
- Randomization
- Amortization
- Basic graph algos
- Combinatorial optimization
- Hardness
algorithms  reference  resource  computerscience  math
november 2016 by mechazoidal
mxgmn/WaveFunctionCollapse
"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
@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
"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
september 2016 by mechazoidal
ferd.ca -> Simhashing (hopefully) made simple
"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
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
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?
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
"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
"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
april 2016 by mechazoidal
ROSALIND | Problems | Locations
Like Project Euler, but for biology instead of math
programming  python  algorithms  biology  puzzles
february 2016 by mechazoidal
\$1 Recognizer
- "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
january 2016 by mechazoidal
angel14995 comments on Why GNU grep is fast
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
"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
october 2015 by mechazoidal
What the Hero Sees: Field-of-View for Roguelikes
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
"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
august 2015 by mechazoidal
How does a relational database work - Coding Geek
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
"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
"A simple proof of concept levenshtein automaton in Python"
python  text  search  github  algorithms
june 2015 by mechazoidal
tobyschachman.com/sketches/minimumpolygon/
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
"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
Topic modeling made just simple enough.
"[...] 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
december 2014 by mechazoidal
Markov Chains
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
Cleverly using fragment shaders to implement maze-solving cellular automata
gpu  maze  pathfinding  algorithms
june 2014 by mechazoidal
per page:    204080120160

Copy this bookmark:

description:

tags: