Making a good random table

April 5, 2016

I am still experimenting with hash functions, and I was toying with the Zobrist hash function[1] that is best known for its use in chess engines. The hash function is conceptually simple: you need a large table of random numbers, indexed, in a chess application, by the position on the board of the piece and by the piece itself. To compute a hash for a whole board configuration, you simply xor all the random numbers together. The hard part is choosing the random numbers.

IMG_0405-small

Read the rest of this entry »


Storage size from bits

March 29, 2016

Last week, we had a look at the computation of Log2 using templates and constexpr. Of course, I had ulterior motives. In particular, I was interested in allocating just the right number of bits for a field in a bit field, but rather than hard-coding it, having it deduced from a template argument. Let’s see how we can do that.

Read the rest of this entry »


Log2 (with C++ metaprogramming)

March 22, 2016

C++ meta-programming a powerful tool. Not only can you use it to build generic types (such as the STL’s std::list), you can also use it to have compile-time evaluation. Let’s have a look at a simple problem that can be solved in two very different ways: computing the Log base 2 of an integer.

Read the rest of this entry »


Rotating Arrays (part II)

February 16, 2016

Last week we had a look at Kernighan’s algorithm to rotate an array k position and concluded that it might not be optimal, as each element was moved twice. This week, we’ll have a look at another algorithm that moves some items more than once, but overall will do less than two exchanges per items.

Read the rest of this entry »


Rotating Arrays (Part I)

February 9, 2016

To “rotate” an array k position to the left (or to the right, doesn’t really matter) we could repeat k times a shift of one, using only one temporary variable. This method doesn’t use much auxiliary memory but is inefficient: it will do kn copies if we apply it to an array of size n. Surely we can do better.

Read the rest of this entry »


Selection, Revisited.

February 2, 2016

When we think of searching, we generally think of searching a value in a sorted collection of some sort. For a simple array, this implies the array is sorted and that we use binary search or a variant. But what if we want to search by rank? In a sorted array, that’s not very hard: the kth item is in slot k. But what if the array is not sorted?

Read the rest of this entry »


LaTeXify C/C++ code snippets

January 26, 2016

So I’m still writing lecture notes. This time, I need to include kind of larger pieces of C or C++ code, and \LaTeX environments do not really help me a lot. Some are better than others, but you still have to escape and fancify text yourself. This is laborious and error-prone, and is an obvious target for automation. A script of some sort. The task isn’t overly complicated: highlight keywords, and escape symbols like { } _ and & that make \LaTeX unhappy. This looks like a job for
sed.

Read the rest of this entry »


Follow

Get every new post delivered to your Inbox.

Join 109 other followers