Simple Random Generators

We all need (pseudo)random numbers sooner or later. Are they hard to generate? Depends. If you want them to be really strong (that is, very random), yes, it’s difficult. If you merely need something random-looking, well, you still need some number theory, but it’s rather not complicated.

Let’s have a look at three simple types: additive, multiplicative, and the infamous linear congruential generator.

Two Features I’d Like to See in C and C++

This week, let’s discuss two features I’d really like to see in C and
C++; one trivial, one not so trivial.

Scanning for π

In a previous episode, we looked at how we could use random sampling to get a good estimate of , and found that we couldn’t, really, unless using zillions of samples. The imprecision of the estimated had nothing to do with the “machine precision”, the precision at which the machine represents numbers. The method essentially counted (using size_t, a 64-bits unsigned integer—at least on my box) the number of (random) points inside the circle versus the total number of points drawn.

Can we increase the precision of the estimate by using a better method? Maybe something like numerical integration?

Computing Binomials (Part I)

We often start thinking about something, make some progress, and eventually realize it’s not going anywhere, or, anyway, the results aren’t very phrasmotic—certainly not what you hoped for. Well, this week’s post is one of those experiments.

So I was wondering, how can I compute the binomial coefficient, , and minimize the size of the integers involved?

The conjecture of 8

The other day I found an amusing short from numberphile about “happy numbers”. Not unlike the Collatz problem, a number is happy if, through successive transformations, it reaches one. The transformation is rather numerological in nature (i.e., it’s arbitrary and so why not): To get the next number in the series to happiness, you take the current number and sum the squares of its digits.

The example in the video is that is a happy number:

Therefore is a happy number. That’s cool, but are all numbers happy, and, if not, what happens when a number is unhappy?

Euclid and Primality Testing (III)

So in previous installments, we looked at how to use the euclidean algorithm to devise a Las Vegas-type algorithm for primality testing. We also found that, in general, simply testing factors one after the other is much more efficient (but that doesn’t mean that there are not better algorithms to test for primality!).

We also considered only relatively small primorials (the products of the first prime numbers) since they rapidly exceeded . But just how fast do primorials grow?

Euclid, Primes numbers, and a Bit of Algorithm Analysis

Last time we had a look at using the greatest common divisor and Euclid’s algorithm to devise a Las Vegas algorithm for primality testing. We also had a look at how the inclusion exclusion principle helps us determine the proportion of the numbers correctly tested.

However, we finished by asking ourselves if the method is actually efficient compared to, say, simply testing small divisors, one by one. Let us now find out.

Fast Path Finding (part II)

Last week we had a first look at a simple path finding algorithm with application to games. This week, let us have a look a the relative performance of the implementations considered: C# with a naïve implementation that scans the whole map multiple times; a C# implementation that uses lists to maintain and visit only the border of the solved region (affording massive speed-ups, one hopes); and C++ versions of these two variants, plus a C++ variant that uses set (as bitmaps) to maintain the border list.

In any quantitative study, the first thing to do is to collect data. The best way is to automate the collection, by, for example, adding a function that puts the player in all legal positions on the map, compute all the shortest paths, and measures how long it takes. One may also consider disabling the on-demand power policy as the CPU may jump (progressively?) in high gear as the data collection progresses, introducing bias.

Fast Path Finding (part I)

The other day in class I was telling my students that sometimes simple strategies simply do not cut it. As an easy-to-understand example, I discussed the behavior of baddies in video games. If your game asks for the baddies to chase the player, the first thing you might try is to move the baddies in the direction of the player, without any other sophistication.

So the algorithm in this case is that you move the baddie closer to the player (or try to, as there might be obstacles), and this translates to something like two lines of code:

Test Drive (more GPS data)

In a few previous entries, we looked at how to capture, parse, and evaluate the precision of a NMEA-capable GPS. The next step is to take it on a test drive.

The setup is simple: a laptop, a USB GPS, a car, and a map. The map is provided by Google Maps, of course. The car and the laptop do not really matter (as long as one of the two runs Linux and has a USB port); the USB GPS is the Columbus V800.