Stallman facts in an Octave release

And now for something completely different…

I managed to get an easter egg into Octave. I’ve always been a little sad that we are not having enough fun in Octave, so I added some facts about the world’s greatest hacker to the source tree. Just type

fact

in the Octave interpreter to read them.

Giving credit where credit is due, thanks to Stallmanfacts.com and to Reddit for starting the whole thing.

Note: I cleaned up the facts a little, removing or amending the ones that were stupid or inflammatory. But this is ok, because these facts are obviously free software under the terms of the GNU General Public license version 3 as published by the Free Software Foundation, or, at your option, any later version? Right? ;-)

ARPACK situation

An open letter to all ARPACK users and developers

I’m writing this email to discuss the future of ARPACK. The problem is this: it’s a widely-used library, but it seems abandoned upstream (and upstream, to whom this is addressed, can confirm or deny). This has resulted in the problem of many mini-forks as each organisation distributes ARPACK patches its own way, and very often, for the same bugs. These are the ones I could find:

Additionally, the Mathworks (they make Matlab) probably also has their own version of ARPACK, but I wasn’t able to find a public version of it, nor an email to send them questions to. If someone could contact them, it would be nice to let them know.

These all seem to have modified ARPACK in some way, with minor or major bugfixes, and as far as I can tell, have mostly done so independently. To me, this seems like unnecessary work, if we’re all patching the library again and again and making our own private forks. What I therefore propose is to have some sort of central location for it and we all pool our efforts on this one location. I think it would be easiest to use Andreas Klöckner’s existing fork on github, since this requires the least maintenance and work from anyone. All that it requires for now is for each of the people above to see what patches they have made and transplant them to the git repo.

It would be helpful if upstream could confirm that they are happy with ARPACK development continuing on github and mention this on the ARPACK webpage, so that new people who are interested on ARPACK can be redirected.

Thanks,
– Jordi G. H.
GNU Octave developer

How to write a patch for Octave

Often people will find ways to improve Octave’s source and provide a patch, but in a way that is slightly inconvenient to analyse and apply. I will now present instructions for creating a patch for Octave in a manner that is easiest for core Octave developers to apply. In what follows, I assume that you have already managed to install Mercurial, that you’re using some sort of shell (probably even Windows), and that hg is already in your shell’s PATH.

First, you should work with an hg clone of the repository:

hg clone http://www.octave.org/hg/octave
cd octave

Once you’re in there, you probably would want to build Octave so you can test your patch. On a Unix-like system, assuming you’ve installed all the dependencies (and that’s a big assumption, because Octave dependencies can be difficult to track down), you should run autogen.sh in the hg clone before you follow the general build instructions.

Then you can proceed to modify Octave sources however you see fit. You can run the hg st command to see which files you’ve modified and hg diff to get a detailed diff of your changes which will eventually become your patch. I personally find the hg colour extension to be a very nice visual aid for these two commands. You should also try to build Octave again with your changes as a minimum sanity check that your patch is good.

A word on building when patching Octave: the deeper in the build dependencies you patch, the longer you’ll spend rebuilding Octave. So, for example, liboctave depends on libcruft, and liboctinterp (most of the stuff under src/) depends on liboctave, so if you touch a file in libcruft, it’s very likely that you’ll have to rebuild liboctave and liboctinterp. The rough depth of things that can be patched by their directory locations is this: libcruft/liboctave/srcsrc/DLD-FUNCTIONSscripts/, in fact, for scripts, you almost never need to rebuild Octave when patching stuff there (unless you want to rebuild the documentation); but sometimes you do need to restart Octave when testing.

Once you think your patch is in good shape, and you’ve written some tests for it (look for assert commands near the bottom of source files to see how tests are written) you should commit it so that it becomes a (semi-)permanent part of your local hg clone. If it’s your first time using Mercurial, you should create an .hgrc on a Unix-like system or Mercurial.ini in Windows and put in there lines to identify you, like so:

[ui]
username = Your Real Name <some@email.com>

Now do

hg ci
hg export . -o my_fix.patch

to record your change. When you type the first command, hg should open an editor where you will now have to write a commit message. Now your change has become part of your local repository, and the second command has exported your patch to a file named my_fix.patch in a format that is easy for others to apply. Now just send that patch to the Octave patch tracker or attach it to an open bug report, and we’ll take care of it!

Complex gcd in Octave

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.