2671
Lovelace's Leap
There's a great deal said about Ada, Countess of Lovelace that I find misguided. And, worse, the real intellectual triumph of Lovelace is ...
New
The latest blog posts to take off on Hacker News. 2,851 posts.
2672
Crit-bit Trees: the best way to store sets
A crit-bit tree can be used as a high-speed associative array. For example, an array mapping 54 to 1, 19 to 2, 99 to 3, 85 to 4, and 88 to 5 can be stored as a crit-bit tree containing 54=1, 19=2, 99=3, 85=4, and 88=5. The smallest string in the crit-bit tree larger than 85= is 85=4.
2673
Latitude doesn’t exactly mean what I thought
There are two kinds of latitude: geocentric and astronomical. On a perfect sphere, they're the same, but on an oblate spheroid like Earth they're different.
2674
Surprises from numerical linear algebra (2010)
Here are ten things about numerical linear algebra that you may find surprising if you're not familiar with the field. Numerical linear algebra applies very advanced mathematics to solve problems that can be stated with high school mathematics. Practical applications often require solving enormous systems of…
2675
Faster pathfinding using Jump Point Search
This is the final article in my three-part look at symmetry reduction algorithms for speeding up pathfinding on uniform-cost grid maps. Recapping the story so far: Part one introduces the notion of…
2676
2677
Compiling to λ-calculus
Though it contains forms only for function applications, variable references and anonymous functions, it is equivalent to a Turing machine.
2678
What does 0^0 equal? Why do mathematicians and high school teachers disagree?
Clever student: I know! $latex x^{0}$ = $latex x^{1-1}$ = $latex x^{1} x^{-1}$ = $latex \frac{x}{x}$ = $latex 1$. Now we just plug in x=0, and we see that zero to the zero is one! Cleverer …
2679
Best algorithms book I ever read
Best algorithms book I ever read I took a fair amount of time looking at data structures and algorithms while I was st...
2680
Do all first links on Wikipedia lead to philosophy?
wikipedia trivia: if you take any article, click on the first link in the article text not in parentheses or italics, and then repeat, you will eventually end up at Philosophy.
2681
2682
A Stick Figure Guide to the Advanced Encryption Standard (AES)
(A play in 4 acts. Please feel free to exit along with the stage character that best represents you. Take intermissions as you see fit. Click on the stage if...
2683
Why Philosophers Should Care About Computational Complexity
Update (August 11, 2011): Thanks to everyone who offered useful feedback! I uploaded a slightly-revised version, adding a “note of humility” to the introduction, correcting the footnot…
2684
Low-level x86 code compression for 64k intros
This is about the “secret ingredient” in my EXE packer kkrunchy, which was used in our (Farbrausch) 64k intros starting from “fr-030: Candytron”, and also in a lot of other …
2685
The Art of Computer Programming (interview with Don Knuth)
While he was over in the UK for a book tour and lecture series, Professor Donald Knuth made time to talk to BCS editor Justin Richards about his life.
2686
Hotelling’s Game, or Why Gas Stations Have Competitors Nearby
There are hundreds of gas stations around San Francisco in the California Bay area. One might think that gas stations would spread out to serve local neighborhoods. But this idea is contradicted by a common observation. Whenever you visit a gas station, there is almost always another in the vicinity, often just across…
2687
Ten Ways to Check if an Integer Is a Power Of Two in C
To write a program to check if an integer is a power of two, you could follow two basic strategies: check the number based on its decimal value, or check it based on its binary representation. The former approach is more human-friendly but generally less efficient; the latter approach is more machine-friendly but…
2688
Donut math - How donut.c works
There has been a sudden resurgence of interest in my "donut" code from 2006 , and I've had a couple requests to explain this one. It's been five years now, so it's not exactly fresh in my memory, so I will reconstruct it from scratch, in great detail, and hopefully get approximately the same result.
2689
Complex numbers have never been so intuitive to me
Imaginary numbers always confused me. Like understanding e, most explanations fell into one of two categories: Gee, what a great way to encourage math in…
2690
2691
Fantastic summary of some of the math pertinent to theoretical computer science.
This web page is a revised and extended version of Appendix A from the book Conceptual Structures by John F. Sowa. It presents a brief summary of the following topics for students and general readers of that book and related books such as Knowledge Representation and books on logic, linguistics, and computer science.
2692
2693
2694
Gray code at the pediatrician's office
From the highly eclectic blog of Mark Dominus
2695
2696
2697
"The worst algorithm in the world?"
You know the Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … Each number is the sum of the previous two. Let’s say the zeroth Fibonacci number is zero, so: $latex \begin{array}{r@{\…
2698
Kill Math
The power to understand and predict the quantities of the world should not be restricted to those with a freakish knack for manipulating abstract symbols.
2699
2700
Smaller than Bloom filters
I've been looking at what would be needed in order to have a global view of CRLs in browsers. At the moment revocation has three problems: privacy (by asking the CA about the status of a certificate you're revealing to them what you're looking at), performance (OCSP checks take hundreds of milliseconds which adds up…