Michael Eisermann

Software (bits & pieces)

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

This page offers the possibility to download 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.

The programming course MAÉ - Mathématiques Algorithmiques Élémentaires (in French) can be found in the section Enseignement > MAÉ.

Disclaimer: The software available from my website is distributed in the hope that it will be useful, but without any warranty whatsoever, without even the implied warranty of fitness for a particular purpose. For details and copyright information see the comments accompanying the source files.

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:

• bimonotone.hh
• example.cc
• taxicab.cc
• sumcubes.cc

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 a³ + b³, 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).

• pick.cc

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