C++ : mt19937 Example

C++11 introduces several pseudo-random number generators designed to replace the good-old rand from the C standard library. I’ll show basic usage examples of std::mt19937, which provides a random number generation based on Mersenne Twister algorithm. Using the Mersenne Twister implementation that comes with C++1 has advantage over rand(), among them:

  1. mt19937 has much longer period than that of rand, e.g. it will take its random sequence much longer to repeat itself.
  2. It much better statistical behavior.
  3. Several different random number generator engines can be initiated simultaneously with different seed, compared with the single “global” seed srand() provides.

The downside is that mt19937 is a bit less straight-forward to use. However, I hope this post will help with this point :-).
Continue reading C++ : mt19937 Example

Enabling C++11 (C++0x) in CMake

Going over some CMakeLists.txt files I’ve written, I came across the following snippet:

include(CheckCXXCompilerFlag)
CHECK_CXX_COMPILER_FLAG("-std=c++11" COMPILER_SUPPORTS_CXX11)
CHECK_CXX_COMPILER_FLAG("-std=c++0x" COMPILER_SUPPORTS_CXX0X)
if(COMPILER_SUPPORTS_CXX11)
	set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
elseif(COMPILER_SUPPORTS_CXX0X)
	set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++0x")
else()
        message(STATUS "The compiler ${CMAKE_CXX_COMPILER} has no C++11 support. Please use a different C++ compiler.")
endif()

Various compiler versions of gcc and clang use different flags to specify C++11 support, namely older ones accept -std=c++0x and newer one -std=c++11. The above snippets detects which is the right one for the compiler being used and adds the flag to the CXX_FLAGS.

Using std::chrono::high_resolution_clock Example

5 years a go I’ve showed how to use clock_gettime to do basic high_resolution profiling. The approach there is very useful, but unfortunately, not cross-platform. It works only on POSIX compliant systems (especially not windows).

Luckily, the not-so-new C++11 provides, among other things, interface to high-precision clocks in a portable way. It’s still not a perfect solution, as it only provides wall-time (clock_gettime can give per process and per thread actual CPU time as well). However, it’s still nice.

#include <iostream>
#include <chrono>
using namespace std;
 
int main()
{
	cout << chrono::high_resolution_clock::period::den << endl;
	auto start_time = chrono::high_resolution_clock::now();
	int temp;
	for (int i = 0; i< 242000000; i++)
		temp+=temp;
	auto end_time = chrono::high_resolution_clock::now();
	cout << chrono::duration_cast<chrono::seconds>(end_time - start_time).count() << ":";
	cout << chrono::duration_cast<chrono::microseconds>(end_time - start_time).count() << ":";
	return 0;
}

I’ll explain a bit the code. chrono is the new header files that provides various time and clock related functionality of the new standard library. high_resolution_clock should be, according to the standard, the clock with the highest precision.

cout << chrono::high_resolution_clock::period::den << endl;

Note, that there isn’t a guarantee how many the ticks per seconds it has, only that it’s the highest available. Hence, the first thing we do is to get the precision, by printing how many many times a second the clock ticks. My system provides 1000000 ticks per second, which is a microsecond precision.

Getting the current time using now() is self-explanatory. The possibly tricky part is

cout << chrono::duration_cast<chrono::seconds>(end_time - start_time).count() << ":";

(end_time - start_time) is a duration (newly defined type) and the count() method returns the number of ticks it represents. As we said, the number of ticks per second may change from system to system, so in order to get the number of seconds we use duration_cast. The same goes in the next line for microseconds.

The standard also provides other useful time units such as nanoseconds, milliseconds, minutes and even hours.

Conditional Compilation in Autoconf and Automake

While working on my audio based random password generator (you view the source in github), I wanted to do some conditional compilation: Compiling certain parts of the program only in case some option is passed to the configure script. As it usually happens with GNU’s autotools, it kind of hell to do it. Documentation is spread across dozens of sources, each provides only a specific part of what to do. I’m writing it here in the blog, in hope I’ll never have to search how to do so again.
Continue reading Conditional Compilation in Autoconf and Automake

Bye Bye OmniCppComplete, Hello Clang Complete

For years OmniCppComplete has been the de facto standard for C++ completion in Vim. But as time progressed, I got more and more annoyed by it’s shortcomings. OmniCppComplete is based on tokenizing provided by ctags. The ctags parsing of C++ code is problematic, you can’t even run it on libstdc++ headers (you need to download modified headers). You want to use an external library? You’ll need to run ctags seperatly on each library. Not to mention it’s inablity to deduce types of anything more than trivial. The core of the problem is that OmniCppComplete isn’t a compiler and you can’t expect something that isn’t a compiler to fully understand code. This what makes Visual Studio’s IntelliSense so great: it uses the Visual C++ compiler for parsing, it isn’t making wild guess at types and what is the current scope – it knows it.
Continue reading Bye Bye OmniCppComplete, Hello Clang Complete

Statistical Tests for My Audio Based Random Number Generator

In May I’ve written about a way to generate random number from audio noise. Basically it went like this:

  1. Get audio sample from the microphone.
  2. Push the least significant bit to a buffer.
  3. Repeat steps 1-2 until the buffer is full (buffer size == block size for the hash function).
  4. Apply the hash function on the buffer.
  5. Get random bits from the digest.

In order to continue developing this random number generator (RNG), I’ve written a C++ class that simplifies working with it.
Continue reading Statistical Tests for My Audio Based Random Number Generator

Simple AI Engine for the Oware Game

Sometime ago I worked with a friend on building an Oware game. I was supposed to build the AI engine, and he was supposed to build the user interface to it. Unfortunately, while AI engine interface I designed and a simple alpha-beta pruning engine was implemented, the project was never completed.

Screenshot of game session
Screenshot of game session

Continue reading Simple AI Engine for the Oware Game

Simple Histogram Widget for wxWidgets

When working on Open Yahtzee 1.10 (or what ever I’ll call the version after 1.9), I’ve written a simple histogram widget to be part of the new statistics dialog. I should emphasize the simple part, this widget was mean to display a simple histogram without requiring any special bloated ploting libraries. It doesn’t support all the fancy stuff, just plain histogram.

I’ve figured that a simple pie plot would better serve Open Yahtzee’s needs, so unfortunately this code will not be released as part of the program. While the code is not perfect, it’s functional and serves a good example of a custom widget. So I’ve felt pity letting it fall into oblivion in Open Yahtzee’s SVN repository, and I’ve thought it might come handy to someone else (or at least for me) if it will be easily accessible.

simple_histogram
Continue reading Simple Histogram Widget for wxWidgets

Convert int to string (As Well As Almost Anything)

This is a little code snippet from Open Yahtzee‘s code base that converts all the built-in types and many custom classes (ones that override the << operator) to string.

template <class T> inline std::string stringify(T x)
{
	std::ostringstream o;
	o << x;
	return o.str();
}

I first wrote it to convert ints to string, but later I templatized it so it would work with other types as well. It’s a clean elegant snippet that I thought other might find useful too.

Expanding Macros into String Constants in C

Today I came across an annoying problem, how do I expand a C macro into a string?

One of C’s preprocessor operators is the # which surrounds the token that follows it in the replacement text with double quotes (“). So, at first the solution sounds pretty simple, just define

#define STR(tok) #tok

and things will work. However, there is one caveat: it will not work if passed another macro. For example,

#define BUF_LEN 100
#define STR(tok) #tok

STR(BUF_LEN)

will produce after going through the preprocessor

"BUF_LEN"

instead of "100", which is undesired. This behavior is due to the C standard noting that no macro expansions should happen to token preceded by #.

However, after reconsidering the source of the problem, I’ve found the following workaround: define another macro which will expand the argument and only then call the macro which does the quoting.

#define STR_EXPAND(tok) #tok
#define STR(tok) STR_EXPAND(tok)

#define BUF_LEN 100

STR(BUF_LEN)

will produce

"100"

as desired.

Explanation: The STR macro calls the STR_EXPAND macro with its argument. Unlike in the first example, this time the parameter is checked for macro expansions and evaluated by the preprocessor before being passed to STR_EXPAND which quotes it, thus giving the desired behavior.