Fair and Square is a problem from the qualification round of Google Code Jam 2013. The gist of the problem is to find out how many integers in a given range are both a palindrome, and the square of a palindrome. Such numbers are called “fair and square.” A number is a palindrome iff its value is the same when written forwards or backwards, in base 10. Continue reading
Binary trees are great. If you ever have to implement one yourself though, you’re probably either using C or you need to look at the documentation for your language’s standard library more closely. Even POSIX C has the tsearch family of functions from <search.h>. Continue reading
This animation is of one of Dimension‘s test scenes, physically integrated with collision detection and gravity. Each collision is perfectly elastic. The 1000-sphere scene was integrated and collision-detected 100 times per frame. The integration and rendering took 30 minutes on 12 cores, or 3 hours of CPU time. Continue reading
These animations, rendered with Dimension, show the ray / bounding box intersections that occur when rendering a single pixel. The first video shows the regular search, and the second shows the faster case of a cache hit, as described in the previous post. Each ray/box intersection takes up one second in these videos, which aptly illustrates the difference between the cache miss and cache hit cases. For this pixel, the improvement is more than a factor of two. Continue reading
PR-trees, as used by Dimension, provide a bounding-volume hierarchy with the unique property of bounded query complexity. Combined with intersection caching, they work as a very efficient BVH, comparable to POV-Ray‘s performance. This is a rendering (using Dimension) of the PR-tree generated for one of its test scenes: Continue reading
Axis-aligned bounding boxes (AABBs) are universally used to bound finite objects in ray-tracing. Ray/AABB intersections are usually faster to calculate than exact ray/object intersections, and allow the construction of bounding volume hierarchies (BVHs) which reduce the number of objects that need to be considered for each ray. (More on BVHs in a later post.) This means that a ray-tracer spends a lot of its time calculating ray/AABB intersections, and therefore this code ought to be highly optimised. Continue reading
Binary-Coded Decimal, or BCD, is the most obvious way to encode a positionally-represented decimal number in binary: literally, 1234 becomes 0×1234. The some of the earliest of early computers used this representation, and the SMS protocol still uses it for some ungodly reason. It also has a more sane role as the expanded version of the DPD encoding for IEEE 754-2008 decimal numbers. Continue reading
It seems that geohot and the members of the group fail0verflow, who found (and in geohot’s case, published) many of Sony’s private signing keys for the PS3 console, are being sued by Sony. I could rant for a while about how everything they’ve done is perfectly legal, and how stupid the DMCA is (I probably will in the future), but actions speak louder than words, so here are the keys that geohot published before he took them down: Continue reading
Facebook has decided to hold a programming competition, I guess. They should definitely hire the winner, and get her to rewrite their damn programming competition interface. But more on that later. Continue reading
Security through obscurity doesn’t work. Every once in a while I like to prove this fact, by getting worldwide high scores on vulnerable leaderboards. The first time I did this was to Area Flat 3 (which was an awesome game when I was in elementary school, and is still pretty fun). Check the all-time top 100 scores for H4X0R (I know, not very original; I was 13, sue me). But that hack was child’s play compared to this one. Continue reading