14/01/2020
In one of the classes I teach, we end up writing assembly language programs. And while I explain the (sometimes very relative) benefits of writing assembly language, I use bubble sort as an example where even carefully crafted assembly language doesn’t mean much: it’s a bad algorithm to start with.

YoU CanT MaKE BuBBleSorT FaSTER With ASseMbLY

Except that it’s not quite true.

Read the rest of this entry »

4 Comments | algorithms, programming | Tagged: assembly language, AVX, bubble sort, Shell sort, sort, sorting, xmm, ymm, zmm | Permalink

Posted by Steven Pigeon

27/02/2018
While searching for old notes—that I haven’t found anyway—I returned to an old blog entry and I thought I was kind of unsatisfactory, with be best part being swept under the carpet with a bit a faery dust, and very handwavingly.

So let’s work-out how to uniformly distribute points on a sphere in a more satisfactory fashion.

Read the rest of this entry »

Leave a Comment » | algorithms, Mathematics, programming | Tagged: Calculus, Curve Length, pseudo-random, random, Sphere, uniform random | Permalink

Posted by Steven Pigeon

09/01/2018
Recently on Freenode channel ##cpp, I saw some code using an include-all-you-can header. The idea was to help beginners to the language, help them start programming without having to remember which header was which, and which headers are needed.

Is that really a good idea?

Read the rest of this entry »

Leave a Comment » | C-plus-plus, hacks, programming | Tagged: C, C Preprocessor, cmath, cpp, cstddef, cstdint, fstream, iomanip, iostream, list, Map, stl, Vector | Permalink

Posted by Steven Pigeon

04/04/2017
Looking for something else in old notebooks, I found a diagram with no other indication, but clearly a low-cost random generator.

So, why not test it?

Read the rest of this entry »

Leave a Comment » | algorithms, Mathematics, programming | Tagged: notebook, PRNG, pseudorandom, simple | Permalink

Posted by Steven Pigeon

27/12/2016
Sometime last week, a tweet from @nixCraft prompted the question, quite ironically, how do you get the maximum (largest positive) value for an integer?

Read the rest of this entry »

Leave a Comment » | C, C-plus-plus, C99, Portable Code, programming | Tagged: CHAR_BIT, intptr_t, INT_MAX, ptrdiff_t, size_t, stddef, stdint, uintptr_t | Permalink

Posted by Steven Pigeon

06/12/2016
More often than I’d like, simple tasks turn out to be not that simple. For example, displaying (beautifully) a binary tree for debugging purpose in a terminal. Of course, one could still use lots of parentheses, but that does not lend itself to a very fast assessment of the tree. We could, however, use box drawing characters, as in DOS’s goode olde tymes, since they’re now part of the Unicode standard.

Read the rest of this entry »

3 Comments | algorithms, data structures, hacks, programming | Tagged: Box, Box-Drawing, Pretty-Printing, recursion, terminal, Tree, Unicode | Permalink

Posted by Steven Pigeon

20/09/2016
Sometimes, you need to compute a function that’s complex, cumbersome, or which your favorite language doesn’t quite provide for. We may be interested in an exact implementation, or in a sufficiently good approximation. For the later, I often turn to Abramovitz and Stegun’s *Handbook of Mathematical Function*, a treasure trove of tables and approximations to hard functions. But *how* do they get all these approximations? The rational function approximations seemed the most mysterious of them all. Indeed, how can one come up with

for , for ?

Well, turns out, it’s hard work, but there’s a twist to it. Let’s see how it’s done!

Read the rest of this entry »

2 Comments | algorithms, bit twiddling, Mathematics, programming | Tagged: Equation System, MacLaurin Series, Padé Approximant, Padé Approximation, Taylor Series | Permalink

Posted by Steven Pigeon

13/09/2016
We’re so used to our positional notation system that we can’t really figure out how to write numbers in other systems. Most of the ancient systems are either tedious, complicated, or both. Zero, of course, plays a central role within that positional system. But is it indispensable?

In one of my classes, I discuss a lot of different numeration systems (like Egyptian, Babylonian, Roman and Greek) to explain why the positional system solves all, or at least most, of these systems’ problems. I even give the example of Shadok counting (in french) to show that the basis used isn’t that important (it still has to be greater than one, and, while not strictly necessary, preferably a positive integer). But can we write numbers in a positional system without zero?

Read the rest of this entry »

5 Comments | algorithms, Mathematics, programming, Science | Tagged: Number system, Positional number system, Shadok, zero | Permalink

Posted by Steven Pigeon

06/09/2016
Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.

But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.

Read the rest of this entry »

Leave a Comment » | algorithms, C-plus-plus, data structures, programming | Tagged: bit, C, Deserialization, Pointers, serialization, Standish, Tree | Permalink

Posted by Steven Pigeon

05/04/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.

Read the rest of this entry »

Leave a Comment » | C-plus-plus, Cryptography, programming | Tagged: /dev/urandom, hash, hash function, pseudo-random number generator, random, Zobrist | Permalink

Posted by Steven Pigeon