# Faster RANLUX Pseudo-Random Number Generators

RANLUX denotes a class of high-quality pseudo-random number generators (PRNGs) with long periods, solid theoretical foundations, and uses in computational physics. These generators are built on top of add-with-carry and subtract-with-borrow PRNGs which allow customization through three user-provided parameters yet there are only two variants in use today working internally with 24-bit and 48-bit arithmetic; this comes at a cost because modern computers do not possess instructions for 24-bit or 48-bit arithmetic. In this blog post I will present the theory behind RANLUX PRNGs, a list of possible parameters for 16-, 32-, and 64-bit RANLUX generators, criteria for selecting generators as well as benchmarks comparing the most competitive RANLUX variants with the RANLUX generators in the C++11 standard library, the Mersenne Twister, and xoshiro128+.

Some of the new RANLUX flavors are easily implemented in C++11 (sometimes in only two lines of code), they are  faster than the existing RANLUX flavors, they retain all desirable properties of a RANLUX generator, and they pass all DieHarder and TestU01 BigCrush PRNG tests.

The programs used to compute the RANLUX parameters are called ranlux-tools. They are free software under the terms of the Mozilla Public License 2.0 and can be found online:

# Rademacher Floating Point Library Released

The Rademacher Floating Point Library provides a C++11 class computing random uniformly distributed floating-point values in a given half-open interval [a,b). In comparison to every other existing software, this library

• computes values that are actually uniformly distributed,
• draws randomly from all floating-point values in range,
• avoids round-off errors causing out-of-range values,
• uses only integer arithmetic, and
• works with built-in C++ float types as well with custom floating-point types.

The Rademacher FPL is licensed under the Mozilla Public License 2.0 and therefore free software ("free" as in "free beer" as well as "free" as in "freedom"). The source code can be found online:

# Cover Trees

A cover tree is a tree data structure used for the partitiong of metric spaces to speed up operations like nearest neighbor, $k$-nearest neighbor, or range searches. In this blog post, I introduce cover trees, their uses, their properties, and I measure the effect of the dimension of the metric space on the run-time in an experiment with synthetic data.

# Implicit Type Conversions Gone Wrong, C++ Edition

Consider the following setup:

#include <cstddef>
using namespace std;
// ...
size_t n = 100;
size_t* array = new size_t[n];

The goal is to set every element of the array to the fixed value x.

In C++, an idiomatic way to solve this problem are the functions std::fill (link to documentation) and std::fill_n (link to documentation) from the STL header algorithm. In addition to the fixed value x, std::fill requires a pair of output iterators specifying a half-open range as its arguments whereas the additional argument to std::fill_n is an output iterator pointing to the first element and the length of the container. That is, we could assign to the elements of the array above as follows:

#include <cstddef>
#include <algorithm>
using namespace std;
// ...
size_t n = 100;
size_t* array = new size_t[n];

fill(array, array+n, x);
fill_n(array, n, x);

What made me write this blog post is the following line of code:

fill_n(array, array+n, x);

Here, I accidentally used std::fill_n in place of std::fill but the code still compiles because of the automatic, implicit type conversion (type coercion) from std::size_t* to std::size_t. With warnings enabled (-Wextra -Wall -std=c++11 -pedantic) neither g++ 4.8.5 nor clang++ 3.5 warn about this line and yet this piece of code causes a segmentation fault on my computer whenever it is executed.