That’s true: the last post was exactly 5 months ago, but I’m still alive! A lot of new stuff happened during these 5 months. Two days after writing the last post, I went with my group (Foundations of Programming) to a very nice hotel in Ruddington, where, during two days, each member had to present something about his/her work. I’ve talked about a result I’ve derived related with distributivity through the Greatest Common Divisor. My slides are available at the event’s webpage and I will put online a note with all the details.
A few days later Alexandra got ill with some strange pain in the abdominal area. The following weeks were really hard, since she had to go to the hospital emergency services. So that you have an idea of how strange the whole thing was, the doctors still don’t know what the problem is! Now, she has occasional pain, but it seems to be much more controlled.
Anyway, more or less at the same time I started to read a very nice article (a Functional Pearl) written by Jeremy Gibbons, Richard Bird and David Lester named “Enumerating the Rationals“. The paper presents some algorithms encoded in Haskell to enumerate the positive rational numbers. In particular, it presents algorithms to construct the famous Stern-Brocot and Calkin-Wilf trees. It also presents a very efficient algorithm to enumerate the rationals in Calkin-Wilf order just by using as current state the previous rational (i.e., two integer numbers). However, the authors claim that “it is not at all obvious” how to create a similar efficient algorithm for enumerating the rationals in Stern-Brocot order. Well, after reading it, Roland (my supervisor) and me found a way of doing it. The key idea is that rational numbers are pairs of coprime numbers (numbers which greatest common divisor is 1) and thus, we can use Euclid’s algorithm as a basis for enumerating these pairs. By using the Extended Euclid’s algorithm written using matrix multiplication, we were able to derive both Calkin-Wilf and Stern-Brocot enumerations from the same algorithm. We wrote a paper named “Recounting the Rationals: Twice!” that was submitted to the journal American Mathematical Monthly.