Это Сан Франциско, город в стиле диско

Jordi

Pretty awesome day in the Bay Area today. The Russians summarised it so a couple of decades ago:

We went to the computer history museum, I discovered that I have a bit of talent for Dance Dance Revolution and loved it (how did I manage to let that game intimidate me all this time and didn’t even try playing it?), rollerskated like I hadn’t in years, and finished the day really awesomely meeting up with very cool people that I only knew from the internet.

There’s a chance to do more things tomorrow, all equally fantastic as today. This has been quite a productive trip! It remains to be seen if its ultimate goal was achieved. They said I would get an initial response very soon.

Andrew S. Tanenbaum, where have you been all my life?

Jordi

I’m currently reading Modern Operating Systems by Mr Tanenbaum in preparation for an important interview, and I have to stop to interject, what a fantastic book. I wish I had come across it earlier. It has very lucid and detailed explanations of many workings of computers that I have long wondered about but never had been able to study.

Bit of background here. As I like to say, I went to maths school, not to computer school. At the time, the choice was quite a conscious one. I knew that computers would always be in my life, and that contrary to making them a more central part of my life, I could always do that on my own, but I needed the formal training to make sure mathematics always kept that central position too. And I do indeed almost instinctively keep on working with computers, as I am doing now with this book. At the same time, not having gone to computer school often makes me feel that I’m at a slight disadvantage with those who have. How to parse a programming language and build a compiler, how to do proper software architecture design, various ways of programming, how an operating system is built, the various concurrent programming algorithms; these are all things you learn in computer school, but not in maths school.

I am not complaining. I learned many other things in maths school, and when I see CS students or programmers balking at mathematics, I chuckle inwardly (and sometimes, I’m embarrassed to say, outwardly). I also learned how to program in maths school, but in a different way, with an emphasis on good numerical algorithms, not the other things they teach there.

In this regard, this book is a treat, because I feel like it’s filling the gap that my formal education didn’t, and it’s also vindicating my decision that I should have studied maths, because the computer part would always draw me throughout life. By comparison, I require much more self-discipline to absorb completely new mathematical material, but a programming language, technique, idea seems to be much easier to be passively assimilated.

By the way, in case the name sounds familiar to you, Mr Tanenbaum is the creator of MINIX, an academic operating system that was the original inspiration for Linus to work on the penguin-clad operating system kernel that bears his name. If I had known earlier that such a book existed, I would have done my best earlier to get it.

I’m reading the third edition, which right now is still refreshingly recent. Computer books age extremely quickly, so it’s nice to read one that’s not outdated for once. I’m also reading it in Mexican Spanish, because it’s what I could find, but I’m not complaining about this either. The translation is wonderfully done, and I really like almost all of the translation choices made. I’ve noticed that Mexicans tend to be much more industrious and precise about technical English translation, whereas most other hispanophones resort to unimaginative calques or leave the English outright untranslated. Rummaging in Spanish for just the right word is work, too much work for some, but in the end it produces much more beautiful text. For example, “deadlock”, a very Anglo-Saxon word with a meaning difficult to convey, becomes “interbloqueo”. Such precision of language! Brief word, same meaning, Latin roots, and even English speakers can guess its meaning. I wish Spanish could develop its own technical language tradition, but that’s a blogpost for another time.

Octave documentation

Jordi

Yay, another patch of mine accepted into the Octave repository. Quite a trivial patch, but at least it was applied without hassle or modification. Maybe because it was only a documentation patch? I’ve got one other documentation patch in the works about coding standards for m-scripts distributed with Octave, which isn’t explicitly described anywhere. I think I will keep trying to submit more documentation patches. They’re quite easy and are obviously necessary.

I wonder how many patches until they give me push access to the repository. I think I still need quite a few before I earn my wings. There’s a big one for printing bitmaps on the fltk backend without going through gs that I would like to do. Maybe this weekend?

TODO created

Jordi

So using Emacs’ org-mode, I’ve written a TODO list. It’s my list of tasks for the various projects I’m involved in. It’s quite fanciful for now, but at least I am certain that all the tasks in it are doable, with a modicum of effort.

The advantage of using org-mode is that I can keep the list updated with it and all the other nifty things that org-mode can do. This Emacs mode really seems like a world in itself. Indeed, many people seem to use Emacs only for org-mode. Perhaps I will soon start to appreciate its mystique.

We’re back in the air!

Jordi

My laptop Iris is back from the shop, and it’s totally like this:

There was a bit of a mixup in that her keyboard is now the wrong layout, but they promised me that they would order the previous layout (US layout, baby, big backslash keys, no L-shaped enter key!).

For now, I got a huge backlog of patches for Octave and LiDIA that I should have written but haven’t. I’m thinking of actually putting up a semi-permanent TODO page.

Iris in the shop

Jordi

Iris is my laptop. She’s a Dellbuntu, which may soon become a collector’s item. About two weeks ago, I spilled some tea with sugar on her. She worked for a week after that, but her keyboard died unexpectedly a week later. I know, I know, I should have foreseen it, should have cleaned her, but I thought I was in the clear when she mostly worked fine, until one day the keyboard completely died.

So, now she’s in the shop. I have to wait for the parts from Dell to come across the border, which they tell me will happen this Friday. In the meantime, I’ve been using public and borrowed computers, and this has only reminded me how much I hate every computer except Iris. I personalise her to such degree that it’s uncomfortable for me to use another computer.

This should all change soon, and she should come back to me safe and sound by this Friday. Can’t hardly wait. Sharing computers is unhyegenic. ;-)

Complex gcd in Octave

Jordi

So I wrote a couple of patches for Octave’s gcd. Jaroslav Hájek rewrote most of a bare bones implementation by David Bateman, but omitted Gaussian integers from the implementation. Octave has integral real types, but only float types for complex numbers, because for some inscrutable reason, C++ itself specifies that std::complex<T> is UB if T is not a float type (i.e., not one of float, double, or long double). Additionally, there were a couple of bugs that I also squashed with my patch.

I’m very happy because this contribution puts me in the 36th place of all of 133 contributors, but head Octave honcho John W. Eaton (jwe) also added my name to the contributor’s list. In other words, this finally puts me somewhere in the Octave map.

So let’s take commemorate the occasion by remembering how to compute the gcd of two Gaussian integers. Let’s begin with the ordinary gcd. Given two integers $$a$$ and $$b$$, their greatest common divisor, denoted $$\gcd(a,b)$$, is an integer $$d$$ such that $$d|a$$ and $$d|b$$ and if for any other $$k$$ such that $$k|a$$ and $$k|b$$, then $$k|d$$. In other words, exactly what it says on the tin, the largest number that divides both $$a$$ and $$b$$.

Now, for the Gaussian integers, i.e. complex numbers with integer real and imaginary parts, it turns out that this also makes sense if by “largest” or “greatest” you mean “largest or greatest in complex norm or absolute value” (technically, we should have also specified that we meant absolute value when we were talking about ordinary integers). The trusty Euclidean algorithm to obtain the gcd of ordinary integers also works for Gaussian integers, because given complex integers $$a$$ and $$b$$ with $$|a| < |b|$$ , you can find a quotient $$q$$ and remainder $$r$$ such that $$a = bq +r$$ with $$|r| < |b|$$. So the basic idea is that you just iterate this division, with the remainders getting smaller, $$|a| > |b| > |r| > …$$ until you get the first nonzero remainder, and that’s your gcd.

As to how to perform the actual division, it suffices to do ordinary complex division and then just round real and imaginary parts to their closest integer in order to get the quotient $$q$$ as above. The remainder $$r$$ is then found by $$r = a – qb$$. You don’t need to round to the closest integer point, since it suffices to pick $$q$$ such that $$|a – bq| < 1/2$$, but rounding is as good a choice as any, as far as I can tell. This does have the peculiarity of picking a particular gcd for the Gaussian integers, since if $$d = \gcd(a,b)$$, then $$-d, id, -id$$ are also gcd's, where $$i$$ is the imaginary unit. This actually also happens in ordinary gcd because $$d$$ and $$-d$$ are both gcds, but there you do have a positive and negative numbers, so you can make an arbitrary choice and pick the positive one. And no, there aren't positive or negative complex numbers, despite appearances. That concept just doesn't make sense for them. I am not sure the division algorithm as described above with rounding is the best way to do it, but I'm not concerned, because it's for Octave, not for a number theory package. I am now mildly curious to investigate what LiDIA does here. Oh, I should also mention, there are many many other rings where the gcd makes sense, such as for polynomials, or in $$\mathbb{Z}[\omega]$$ (Eisenstein integers, the integers plus a cube root $$\omega$$ of $$1$$), but Octave doesn't really have a convenient way to represent other rings. In fact, I'm a little surprised that Octave has a gcd at all, and I doubt many people wanted a complex gcd. Regardless, should anyone try it with complex numbers, they'll see that at least we think of everything.

Linked on Reddit

Jordi

Oh, dear me.

A few years ago, I wrote a strongly-worded opinion piece on just why I believe so strongly on free software. Today it was linked on Reddit. While I do want free software everywhere, and I would like to completely abolish the notion of proprietary software, I see that as a distant dream. My immediate goal, my highest priority is to have free software for mathematics, because I think that hiding source and restricting distribution are the antithesis of mathematical work. Others have other priorities, but for me, free software in mathematics is highest.

In this vein, I wrote this some time ago. It’s a piece many people have read, and it always seems many have an opinion about. Many love it, but also many strongly disagree with it. They cite objections that say that the ends justifies that means, that having a good software package for doing mathematics trumps any need to have its source, that it’s ok to hide source if you’re making money, and that without the money that restricting distribution provides, you wouldn’t have quality software at all.

Needless to say, I believe all of these objections to be false if stated absolutely, as there are plenty of counterexamples to each, of varying degree. Nevertheless, I don’t have the energy to individually present them again, nor to address my detractors in the Reddit comments. I’m both sad and happy when I read those comments, and I wonder which direction the discussion overall will take. As for that beacon in the free software movement, Richard Stallman, whatever you might think of him, you have to admire him for his boundless stamina to be able to tirelessly participate in these discussions, and for being so self-consistent both in words and actions about what software freedom should be.

For the moment, I do not feel like arguing about this anymore. I feel like actions. Talk is cheap. I’ll show you the source. Perhaps we will never amount to anything, perhaps Octave will forever lag behind Matlab in one way or another, perhaps Sage will forever be a patchwork of individual programs of varying quality. Or perhaps not. Regardless, I don’t care. We must proceed. I must proceed. We must do, we must keep faith, because it’s obvious that even if the goal is unattainable, it’s the right goal. I would hardly be a hacker-errant of the rueful countenance if I didn’t think so.

A Personal Introduction to LiDIA

Jordi

LiDIA is a very old C++ library for computational number theory. The copyright statements inside its source say it’s from 1994. I’m not sure if it’s any good anymore, but it probably isn’t the best one out there, although at one time, it did have the best implementation anywhere for doing arithmetic with elliptic curves.

By the way, for those not in the know, number theory is the part of mathematics that studies the integers (whole numbers) and their properties, like divisibility and distribution of primes. It’s admittedly a very broad discipline, and it does at times feel like it’s a patchwork of many different tricks, but number theory does have its own particular flavour. Pari/GP is just about the only other free software package that concentrates on number theory. In fact, the originators of both, Henri Cohen and Thomas Papanikolaou, appear to be close collaborators. Pari’s development has also slowed down but hasn’t stopped, and it helps that it’s an integral component of Sage, so it is getting attention from the mathematical free software community.

I remember reading in some Sage mailing list a very scathing review of LiDIA. It berates LiDIA for being slow, incomplete, and awkward.

LiDIA was officially abandoned in February 2010, and I had been nagging its authors to release it under the GPL for a while. It had been under some awkward makeshift noncommercial license before that. However, this was in 2006, and interest in LiDIA had already almost died by then. Although permission to release under the GPL was granted, nobody seemed to care enough about it to actually make an official free release. Finally, Christoph Ludwig, who was LiDIA’s maintainer for a long time, got around in 2010 to actually put the GPL notice in LiDIA’s sources. I nagged him about adding an “or later” clause to the version (Sage uses GPLv3, so it would need it), which he did. And then officially abandoned LiDIA.

Soon after that, I grabbed the LiDIA subversion repository, converted it to Mercurial, and uploaded it to bitbucket. So how is it doing?

Well… it compiles with a modern gcc, so that’s something. I took the liberty of squashing some bugs by compiling with -Wall and -Wextra warning flags. There were silly bits of code with signed and unsigned integer types like

u--;
if(u < 0)
  u = u + prime;

but u was an unsigned type. :-/ In fact, LiDIA overall plays fast and loose with signed and unsigned type. It has a deceptively-named lidia_size_t typedef that would make you think that it’s some unsigned integral type, like C++’s standard size_t, but no, it’s a signed integral type, and it was in fact just int. The code supposedly would let you typedef it to be long, which I did, but that broke many other things elsewhere. I also tried for about a day to make it semantically correct and make it an unsigned type, but that turned into a cascade of trouble, since a lot of code explicitly requires this typedef to be signed.

Anyways. I also got around, thanks to the suggestion of Matin Ettl, to fix more warnings in the code that Martin Ettl’s cppcheck program found. There weren’t many, only two more about dangerous calls to sprintf, and one about an uninitialised variable.

So where do I plan to go from here? This is just about getting the damn thing to compile, not yet about the actual worth of its code. Well, I plan to keep on plowing with this for a while. I want to be fairly public about my work on LiDIA, with the hope that I may catch someone’s attention (in fact, this is how I caught Martin Ettl’s attention and got a suggestion from him). My immediate plans are

  1. Move the build system to Cmake, because I just don’t get GNU autotools.
  2. Inline the documentation with Doxygen. It’s a blessing that LiDIA actually is extensively documented, even if not always accurately. The problem is that the documentation is separately maintained in LaTeX files, and I’m sure this has contributed to the problem of it going out of synch with the actual sources, so that’s the motivation for this task.
  3. Write some unit tests for it. As it is, right now all I know is that LiDIA compiles, but I have no idea if it’s any good for mathematics.
  4. Squash more bugs as I find them.

I used LiDIA myself in 2003 for an undergraduate research program related to counting points on algebraic curves. I still have that code and it still runs on the current LiDIA sources, but whether it’s accurate or fast, I wouldn’t know. It’s partly due to this youthful infatuation with LiDIA, but also because despite everything, I still like C++, and I do think it’s still the best language in which to write conceptually complex code while staying close to the machine. Furthermore, I think it’s a good opportunity to read about number theory and its techniques, that is, I’m also doing this for my own edification. Lastly, I’m doing this because it might benefit someone in ways I haven’t foreseen.

At any rate maintaining an abandoned C++ number theory library certainly won’t hurt anyone, so why not?

Salve, cronica electronica!

Jordi

Hello, blog!

Hopefully this post is the first of many. I plan to write about several things, both personal and more public/professional.

I must say, WordPress was quite easy to set up, but I’m still not sold on PHP. I had to patch a few things here and there, in particular with this nifty $$\LaTeX$$ plugin that I plan to put to good use. Oh, and while we’re talking about meta, thanks also to Tim Saimburg for this free nifty blog design. I tweaked it a little for some spacing, colours, and font sizes, but just barely. Thanks!

It’s a Saturday afternoon, and I’m tired of tweaking and setting up this blog — which I can barely resist to call “blag”, but I will defer to established use — so I will rest for now and do other things.

FRIST POAST!!!!!