## just_enough

30/06/2020

The C99 <stdint.h> header provides a plethora of type definition for platform-independent safe code: int_fast16_t, for example, provides an integer that plays well with the machine but has at least 16 bits. The int_fastxx_t and int_leastxx_t defines doesn’t guarantee a tight fit, they provide an machine-efficient fit. They find the fastest type of integer for that machine that respects the constraint.

But let’s take the problem the other way around: what about defines that gives you the smallest integer, not for the number of bits (because that’s trivial with intxx_t) but from the maximum value you need to represent?

## Lïtbørd (more than some assembly required)

09/06/2020

As you may have noticed, a global pandemics got many of us working from home. While one can argue that you can do accounting from home, it’s a lot more complicated to teach from home. Pretty much everyone is trying to figure that one out. For my part, I decided that zoom and the virtual whiteboard is not very interesting. Like many, I decided to use a lightboard.

So, the problem is, where do you get a lightboard on short notice? Well, you can build one. Let’s see how:

## Evaluating polynomials

05/05/2020

Evaluating polynomials is not a thing I do very often. When I do, it’s for interpolation and splines; and traditionally those are done with relatively low degree polynomials—cubic at most. There are a few rather simple tricks you can use to evaluate them efficiently, and we’ll have a look at them.

## Factorial Approximations

31/03/2020

$n!$ (and its logarithm) keep showing up in the analysis of algorithm. Unfortunately, it’s very often unwieldy, and we use approximations of $n!$ (or $\log n!$) to simplify things. Let’s examine a few!

## How many bits?

24/03/2020

In this quarantine week, let’s answer a (not that) simple question: how many bits do you need to encode sound and images with a satisfying dynamic range?

Let’s see what hypotheses are useful, and how we can use them to get a good idea on the number of bits needed.

## YoU CanT MaKE BuBBleSorT FaSTER With ASseMbLY

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.

## Fast Exponentiation, revisited

12/11/2019

Quite a while ago, I presented a fast exponentiation algorithm that uses the binary decomposition of the exponent $n$ to perform $O(\log_2 n)$ products to compute $x^n$.

While discussing this algorithm in class, a student asked a very interesting question: what’s special about base 2? Couldn’t we use another base? Well, yes, yes we can.

## rdrand

04/11/2019

Last week (at the time of writing, anyway), Ars Technica reported a serious bug in AMD’s implementation of rdrand, an instruction that helps you generate random numbers. Apparently, on (some) Ryzen 3000, 0xfff…ff is “random”.

I recently got an AMD Ryzen 9 3900x, and I wondered if I have the bug as well.

## (Sub)bit-fields (Coding with fractions of bits, Part II)

13/08/2019

Last week, we used the 6×7×6 palette as an example of very simple fraction-of-a-bit coding1. However, we can generalize still a bit more to allow single field extraction and modification

## The 6×7×6 palette (Coding with fractions of bits, Part I)

06/08/2019

Remember ye olde dayes when we had to be mindful of the so-called “web safe palette“? Once upon a time, screens could display 24-bits colors, but only 256 at a time in some “hi-res” modes. But that’s not what I’m going to tell you about: I’d rather tell you about the encoding of the palette, and about a somewhat better palette. And also about using fractions of bits for more efficient encodings.