Functional list processing in C# 2.0 with anonymous delegates

One of the benefits of functional languages is their great flexibility in list manipulation, which enables them to express certain computations concisely that would require one or more verbose loops in procedural languages. Many of the features that functional programmers take for granted such as first class functions, persistent data structures, and garbage collection were included in…

12

Factoring large numbers with quadratic sieve

Today I’m going to talk about how the quadratic sieve factoring algorithm works, giving a comprehensive description assuming knowledge of only basic university-level mathematics. The foundation of the most popular public-key cryptography algorithm in use today, RSA, rests on the difficulty of factoring large integers. When keys are generated, efficient algorithms are used to generate…

20

Color quantization

If you’ve ever done work with Web graphics, I’m sure that at some point you reduced an image with thousands of colors, such as a screenshot or photograph, to an image with only 256 colors, for example to store the image in the GIF format. Remarkably, the reduced image is usually very visually similar to…

8

How does JPEG actually work?

JPEG is an image encoding designed to compress photographs and similar images effectively, often 5 to 15 times over a raw bitmap format. It’s a lossy format that exploits properties of human vision to eliminate information that is difficult to distinguish. You see JPEGs all the time, and if you’ve seen a JPEG compressed with a low…

7

Encoding correctness in types

This article will discuss effective use of types to catch some common problems at compile time not normally found by the typechecker. The typechecker is the most important tool in the programmer’s arsenal. Types enable you to structure code in a more maintainable way and prevent entire classes of errors from ever occurring at runtime,…

0

LiteratePrograms wiki

Hi everybody. This is a short post, but I just wanted to tell you all about a new wiki I created called LiteratePrograms, based on an extension of the same MediaWiki software used by Wikipedia. Some of you read my earlier post about literate programming and some of the advantages it has for easy-to-read exhibition of…

0

Dependency tracking in builds

Happy Valentine’s Day, everyone! Today I’m going to talk about the important problem of successfully tracking dependencies in builds in an automatic manner. In short, there are two kinds of build systems: the ones where all dependencies are tracked successfully and incremental rebuilding is available at all times, and the ones where you have to…

6

The nature of computing and infeasible machines

If asked what they do, some developers might say “I write code” or “I program computers”. But more fundamentally, what is computing really about? After all, Euclid’s algorithm for computing the greatest common denominator of two numbers in polynomial time was designed – and executed by hand – thousands of years ago, long before even…

3

Literate programming

Literate programming, invented in 1981 by the same Donald Knuth who wrote The Art of Computer Programming and the document language TeX, is a technique in which a program is written as a human-oriented document interspersing discussion and code. The code segments are arranged not according to execution order or the logical structure of the…

10

Efficient selection and partial sorting based on quicksort

Most people who have studied algorithms remember quicksort, the ubiquitous sorting algorithm available in the standard library of nearly every programming language implementation in existence, including C, C++, Java, and the .NET Framework. Quicksort is a compelling example of how algorithms with poor worst-case behavior but good average-case or expected behavior can be highly practical. Much…

6