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.
Leave a Comment » | 
algorithms, C, C-plus-plus, Mathematics | Tagged: Estrin, Horner, Parallelism, Polynomial, SIMD | 
Permalink
Posted by Steven Pigeon
Leave a Comment » | algorithms, Mathematics | Tagged: approximation, Factorial, Gosper, Mohanty, Rummens, Stirling | Permalink
Posted by Steven Pigeon
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.
4 Comments | algorithms, programming | Tagged: assembly language, AVX, bubble sort, Shell sort, sort, sorting, xmm, ymm, zmm | Permalink
Posted by Steven Pigeon
Quite a while ago, I presented a fast exponentiation algorithm that uses the binary decomposition of the exponent 
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.
2 Comments | algorithms, Mathematics | Tagged: base 2, binary, fast exponentiation, Mathematica, number theory | Permalink
Posted by Steven Pigeon
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
2 Comments | algorithms, data compression, data structures | Tagged: Arithmetic Coding, bit-field, fractional bits, Palette, sub-bit | Permalink
Posted by Steven Pigeon
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.
1 Comment | algorithms, data compression, hacks | Tagged: bit, coding, colorspace, log, web safe palette | Permalink
Posted by Steven Pigeon
While this sounds something like a shameful family secret, discrete inversion is only the finite-valued variation on the method of inversion for the generation of random numbers with a given distribution (as I’ve discussed quite a while ago here). The case we’ll consider here is a random variable with few possible outcomes, each with different odds
Leave a Comment » | algorithms, C-plus-plus | Tagged: discrete random variable, initializer_list, inversion, probabilities, pseudo-random, pseudo-random number generator, Random Variable, uniform random | Permalink
Posted by Steven Pigeon
