Michael Eisermann

Hofstadter's Law: It always takes longer than you expect,
even when you take Hofstadter's Law into account.
Douglas Hofstadter, Gödel, Escher, Bach

Software (bits & pieces)

This page presents some of the source code I have implemented in C++. For the time being the list is very short. New items will be added every now and then.

For the programming course Mathématiques Algorithmiques Élémentaires (in French) please confer to the section Enseignement > MAÉ.

Bimonotone enumeration

Solutions of a diophantine equation f(a,b)=g(c,d), with a,b,c,d in some finite range, can be efficiently enumerated by sorting the values of f and g in ascending order and searching for coincidences. D.J. Bernstein has applied this approach with great success to equations of the form p(a)+q(b) = r(c)+s(d) , as explained in his article Enumerating solutions to p(a)+q(b) = r(c)+s(d). I have generalized this approach to arbitrary bimonotone functions in my article Bimonotone enumeration. The algorithms developed therein have been implemented as class templates in C++ and are available for download:

Here bimonotone.hh is the main file: It implements the bimonotone enumeration algorithm as a class template in C++. Its usage is illustrated by the program example.cc. The program taxicab.cc searches for multiple values of the polynomial a3 + b3, that is, taxicab numbers. It uses the file sumcubes.cc that implements the basic calculations (with various possible optimizations).

For which triangles is Pick's formula almost correct?

We consider triangles Δ = [ (0,0), (p,0), (p,q/p) ] parametrized by two positive integers p and q, and compare its area, denoted Area(Δ), to Pick's lattice point count, denoted Pick(Δ). Of course, if q/p happens to be an integer, then Δ is a lattice-triangle and Pick's classical theorem says that Pick(Δ) = Area(Δ).

For certain non-lattice triangles Pick's formula is almost correct in the sense that either Pick(Δ) = Area(Δ) or Pick(Δ) = Area(Δ) + ½. Quite surprisingly, there exist triangles Δ such that Pick's formula is almost correct for Δ and all magnifications rΔ where r is a positive integer. Such examples are not obvious and remain difficult to understand.

Besides mathematical amusement, the quest for such triangles has its origin in knot theory, as explained in our note For which triangles is Pick's formula almost correct? Casson and Gordon have found four infinite families, and a long-standing conjecture says that these are the only solutions. The following computer program serves to test this conjecture empirically (and as extensively as you may wish).

Wirth's Law: Software is getting slower
more rapidly than hardware becomes faster.
Niklaus Wirth, A plea for lean software