Posts

  • Generating Equidistant Points on a Sphere

    In this post I’ll revive work I did during my PhD to generate 3D points that are equally spaced on the unit sphere. Such equidistant points are useful for many operations over the sphere as well as to properly tesselate it. The method is based on a spiral walk of the spherical surface in angular increments equal to the golden angle. The golden angle is related to the golden ratio.

  • The High Performance Time-Stamp Counter

    Your computer has a high performance Time-Stamp Counter (TSC) that increments at a rate similar to the CPU clock. On modern processors this counter increments at a constant rate and may be used as a wall clock timer. The benefit of the TSC compared to the Linux system timeofday or clock_gettime functions, for example, is that the TSC takes only a few clock cycles to read.

  • A Fast, Compact Approximation of the Exponential Function

    The exponential function and specifically the natural exponential function exp is used often in machine learning, simulated annealing and many calculations within the sciences. Part of the reason why the natural exponential is so useful is that it is quite unique in that it is its own derivative. Put differently, the slope of the function is equal to its height. A fast non-table-lookup approximation of the natural exponential function would be very useful to accelerate many applications of exp.

  • Making Fire and Water

    Future Crew’s 1993 PC demo called Second Reality had a Brobdingnagian impact on my interest in programming. Much of what I researched and played with at a young age was due to this demo. The demo won a couple of prizes and eventually made it onto Slashdot’s Top 10 Hacks of All Time. The source code which contains lots of PAS, POV and ASM files was released to celebrate the 20th anniversary of the demo. A high quality video of the demo is also available.

  • The Heap Allocation Behaviour of the C++ std::unordered_set

    Hash tables are very useful whenever a constant time lookup of a key or key-value pair is required. It is therefore good to know how these containers are implemented and used. The C++ std::unordered_map and std::unordered_set are good examples of a hash table and hash set respectively. This post will investigate the heap allocation behaviour of std::unordered_set. One can expect the behaviour of std::unordered_map to be similar.

  • The Performance of C++ std::deque vs. std::vector

    Many algorithms make use of a double ended queue (a.k.a. a deque). For example, in breadth first search a deque is used to hold the search frontier. Having a fast implementation of a deque is very useful.

  • The Intel DRNG

    I recently got around to testing Intel’s Secure Key Digital Random Number Generator (DRNG). Intel Secure Key (code-named Bull Mountain Technology) is the name for the Intel® 64 and IA-32 Architectures instructions RDRAND and RDSEED and the underlying hardware implementation.

  • The Knapsack Problem

    The knapsack problem comes up quite often and it is important to know how to solve it. For example, given a certain material budget and the cost vs. perceived value of building various edges in a potential road network, which edges should one build? The goal is to optimise the perceived value of the built roads within the fixed material budget.

  • First post with Jekyll

    Jekyll is pretty cool. I followed the Quickstart guide which generates a basic blog site using the minima theme. Once you push the source to your https://github.com/<username>/<username>.github.io repo, Github Pages will build your site and make it available online at <username>.github.io. You can see what the site looks like locally before pushing by running bundle exec jekyll serve --drafts and pointing your browser at 127.0.0.1:4000.

subscribe via RSS