6 ms·
The Most-Used Mathematical Algorithm Idea in History (2016)
- bransonf 6y agoAmazing... learning of the existence/term of polyominoes is a breakthrough for me. I’ve recently been working on developing a novel statistical test to quantify sensitivity to the modifiable areal unit problem (MAUP). The limiting factor has been the ability to efficiently generate arbitrarily shaped polygons on a lattice at random. In essence, this is needed to stochastically reallocate a spatial characteristic and measure variance. Apparently, the exact solution I’m looking for is Donald Knuth’s algorithm X [0]. And I also found this interesting application of the algorithm [1]. I simply cannot express how much my curiosity has just peaked. Moreover, I now have reason to cite both Solomon Golomb and Donald Knuth in a paper. [0] https://en.m.wikipedia.org/wiki/Knuth%27s_Algorithm_X https://en.m.wikipedia.org/wiki/Knuth%27s_Algorithm_X [1] https://gfredericks.com/blog/99 https://gfredericks.com/blog/99
- kian 6y agoCuriosity peaking (I have also seen peeking) is quite an interesting mondegreen for curiosity 'piquing'. The latter means 'stimulating' or 'aggravating', whereas the former implies that when you hear about something for the first time your curiosity is at a maximum - which is a fun interpretation :)
- sidpatil 6y agoI wouldn't be surprised if peak and pique have similar etymology.
- knuthsat 6y agoYou might find zero suppressed binary decision diagrams (ZDDs) useful. They also allow simple random generation of all kinds of objects (even constrained ones). Knuth adjusted his algorithm X for ZDD and got some nice speedups.
- amongwhales 6y agoI had never seen polyominoes used professionally for mathematics. However, I was reminded of seeing them in the teen novel Chasing Vermeer [0]. [0]https://en.m.wikipedia.org/wiki/Pentomino#Literature https://en.m.wikipedia.org/wiki/Pentomino#Literature
- melonmouse 6y agoI made a game about polyominoes: https://melonmouse.itch.io/polyominoes https://melonmouse.itch.io/polyominoes If you try it out, please let me know what you think :) P.S. work on that led to a sequence on the Online Encyclopedia of Integer Sequences: https://oeis.org/A239658 https://oeis.org/A239658
- ballenf 6y agoOne QOL consideration: consider allowing the last placed piece to be moved in one click. That is, if you click while "at capacity" the last placed piece gets removed and placed where you click.
- miguelmurca 6y agoKind of a side note, but Stephen Wolfram really has a way to make things about himself.
- BeetleB 6y agoFor many years, this annoyed me. Now, though, I enjoy it. At least he is someone of note.
- arduinomancer 6y agoHow is that your takeaway from the article? There’s a lot of interesting anecdotes/history here. He spent quite a lot of time just talking about Golomb and his work.
- ganafagol 6y agoAn obituary where the author casually drops that he was the youngest receiver of this-and-that award? That everything becomes so easy with the Wolfram Language? That he's written a new kind of science book and casts Golomb's work as essentially a precursor for his great accomplishments about cellular automata? Wolfram is slowly transforming into the Trump of computer science. Soon he'll cast turing machines as just a small precursor of himself having solved computation.
- protastus 6y agoEvery single article I've read by Wolfram makes detours to focus on his own accomplishments (e.g. awards or appointments), tied to the main story by extremely tenuous, almost non-existent connections. And there are always multiple references to cellular automata. I will gladly admit I like his storytelling and the anecdotes are interesting but I have to ignore the detours to make it to the end.
- codeproject 6y agodon't be so harsh on the old man. He indeed accomplished a lot. A little bit self-promotion is generally Ok. What did Steve Jobs actually do technically?
- psychometry 6y agoIf I die famous someday, I really hope Stephen Wolfram doesn't write my obituary...
- yudlejoza 6y agoI hate to admit this, but I'm one of those types too (who you wouldn't want as the authors of your obit). I've been called every name in the book by my own friends, e.g., Dunning-Kruger, "full of it", etc, etc. I know all these terms. I just don't know how to come across as a humble person, despite it hurting in my personal/social/work life. The only thing that helps is if I interact with others less (there I go again).
- SavantIdiot 6y agoIs there a reason why it is called a "Mathematical Algorithm Idea" instead of "Mathematical Algorithm"? The pedant wants to know if that's a specific classification of algorithms, and the gatekeeper in me wants to penalize grammar.
- hehetrthrthrjn 6y agoWhen I saw it I just thought it was needlessly redundant. He could have just said 'algorithm' since it's almost always mathematical in some sense and it's always an idea.
- shric 6y ago> When I saw it I just thought it was needlessly redundant. Isn't "needlessly" redundant there? :p
- mhh__ 6y agoI find that a certain level of redundant language in a sentence or paragraph can allow me to sink different hooks for a reader and thus reduce the likelihood of having to repeat myself. The hook-euphemism is similar in nature but different in application to Feynman's self-labelled "chaotic" approach to teaching
- ganafagol 6y agoRedundancy is often times a feature. Certainly in natural language as it allows for seemless error correction if there is some word you didn't hear or some letter you can't see. Or in computer communications too, like with CRC or similar codes (mentioned in the article).
- mikeyjk 6y agoWhen referring to a comment written online though? I agree with your main point
- hehetrthrthrjn 6y ago
- gigatexal 6y agoAwesome article. I’ve a new hero to add to my list of people I’d thank a million times over for their contributions to modern tech. Thank you Sol!
- sjwright 6y agoI wonder how that would compare to the Fourier transform?
- peteretep 6y agoDid his grand theory of everything ever come to anything?
- YaSamPoSebe 6y agoIsn't that dynamic programming instead? Or more generally, the idea of time-memory tradeoff.
- betterunix2 6y agoPretty sure that honor goes to positional number systems and the arithmetic algorithms like carry-based addition.
- xbar 6y agoRIP Solomon Golomb
- rcgorton 6y agoThe original post is overstated: addition is used FAR more. If you perform a string op, you need addition. If you do a matrix operation, you need addition. ALL polynomial operations that I know of require addition. When you read or write from memory, addition is used
- PoignardAzur 6y ago> And by comparing delay times from different satellites, the receiver can triangulate its position Argh! It's not triangulating, it's trilaterating. Good article, though.