Knitting for geeks

Margarita Manterola from Debian Women asks:

So, after the whole Wikip. thing, I ended up following lots of links
about knitting, and as everytime I come in contact with this, I feel
like I should learn to knit (or maybe I should say, re-learn, I was
taught during primary school, but forgot all about it afterwards).

Is there a “knitting for geeks” tutorial around? :)

There’s tons of videos in YouTube to get you started, although I don’t think many of them are “for geeks” specifically… or at least different kind of geeks. Knitters geek out over types of yarn, needles, complicated patterns, unorthodox knitting, knaughty knitting (e.g. knitting a bra or a thong)… they do end up speaking a special kind of language and getting very passionate about it. What worked for me was when my mom sat down with me to teach me how to cast on, the basic knit and purl stitch, and from then on I was able to bootstrap my first scarf. Perhaps you can learn from videos instead. We didn’t have YouTube when I learned how to knit, heh.

I personally do appreciate a certain mathematical aspect of knitting. I got started because I saw a friend in algebra class in university (y’know, the Galois theory kind of algebra) do complicated lace patterns with needles while she was listening to the lecture, so I was intrigued (and later in love, long story). My kind of mathematical knitting is usually limited to things like knitting a Möbius scarf (non-orientable knitting!) or a hyperbolic plane (negative curvature knitting!). It’s rather remarkable how with just a few basic stitches you can build very complicated things. It does feel a little like Turing machines!

If you need a book, I rather like the Vogue knitting series myself. I hear Stitch’n’Bitch is popular. And most knitting magazines also have introductory instructions in every issue. I liked Knit 1, another Vogue publication, or you can read Knitty online. Knit 1 seems to have ceased publication, but you can probably find back issues in your LYS[1].You might also want to find people near you to knit with, in which case language can be a slight hurdle at first. I really enjoy social knitting. I actually get a little lonely when I can’t find people to share my knitting with.

Incidentally, it’s kinda interesting how knitting patterns are a lot like source code, with similar kind of politics. People share them, remix them, some jealously guard them and try to sell them, others want to ensure as many people as possible can compile your knitting instructions… Interesting world, definite parallels with the free software world.

[1] Local yarn store… too bad most knitting distros don’t ship with the wtf(1) binary. ;-)

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
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 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:

username = Your Real Name <>

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!

Earning my wings

I forgot when it happened, but it was sometime in late January or February that I was finally given push access to the Octave repositories, plus being a manager for Octave items at the Savannah website where it’s hosted. This means I have the privilege to commit my changes to Octave code on my own without needing to ask someone to push them for me, plus I can also handle bug reports to Octave on my own. In addition to that (bring it on, spammers!) I also now have an mailing address.

This is a pretty big deal for me. I had been dreaming of being a formal member of the Octave dev team, and I’m really glad it’s finally happened.

At the same time, I wanted to get this distinction because I had obviously earned it… but what actually happened is that I obliquely requested it and head honcho jwe responded to it.

I’m a junior Octave dev, and I expect to be one for a while until I get to feel more comfortable with the code base. This means that I still need to be very careful with what I push, and I should consult publicly on the mailing list if my patches are acceptable before I push them.

So what have I done so far with my shiny new Octave badge? So far as I write this, not much only 8 changesets, of which 6 are documentation fixes, one was a minor m-script fix for imshow, and the last fix as I write this that looks like a minor thing, but took I would say around 30 hours of debugging to find. The Nikolai Tesla fable comes to mind.

I have done other things that don’t show up in the hg log. I try to help as much as I can in the mailing lists and in the #octave channel in Freenode. I’ve been trying to help triaging bug reports in Savannah. I’ve revived work on Agora a little. A friend has lent me hosting for it! Snippets are now fully functional as far as I’m concerned. I even created a better Octave syntax highlighter for Pygments, although I’m still waiting for the official Pygments maintainer to pull my patches. It really does work, although I gotta fiddle around with the setup in my shiny new webhost to make it work.

I’m going to keep working in the immediate future on the sparse matrix bugs I’ve been looking at. Squashing #32747 was a lot of fun, and it forced me to finally use a good gdb setup, plus learn more about gdb itself. Wow. What an awesome debugger.

And as I keep working on Octave, perhaps I’ll feel more justified for the Octave badge that has been handed to me, feel like I actually earned it, not that I just asked for it and jwe is just a generous guy.

I don’t hate git as much anymore…

So a partial retraction to my previous post…

It turns out that git has something called a reflog, which seems to be purely documented in the git-reflog(1) manpage, and to my taste, rather tersely. It appears that git does keep at least a partial log of recent operations so it’s possible, with varying degrees of success, to undo past operations. Or at least this was the theory I read scattered across several bits of oral tradition like personal webpages and blogs and what I could glean from the manpage.

I didn’t see any commands to actually recover data from the reflog, only to read what’s in it. Regardless, at least I was able to recover a few of the branches that git deleted remotely and from reading the commit messages, which I hadn’t noticed before, I was able to guess where the remaining accidentally deleted branches were.

So, anyways, git does have a recovery mechanism… somewhat… It’s about the same way that it’s still possible with some luck do an undelete on an ext3 filesystem. In other aspects, git is still too complicated and dangerous for my taste. It’s a little funny because I’m actually quite comfortable with complicated and dangerous tools elsewhere, like good ol’ rm, cp, mv and other dangerous Unix tools where a typo can mean instant data loss. I recognise that perhaps there should be better ways to do this, but I don’t know of one I like. In the case of VCSes, I know of a better, simpler, safer tool than git, and it’s hg. Perhaps it’s because I have an alternative and feel proficient with it that I prefer it to git.

I will use git again, very cautiously. It’s not a VCS where I can experiment widely without fear, because git erases data remotely. It’s however unavoidable due to its popularity, and I will need to acquire some fluency with it if I’m to keep collaborating with people who use git. For my personal use, I don’t see myself moving away from hg for quite some time to come.

La Red Social

I just watched the Facebook movie, The Social Network, or whatever, La Red Social en español. I started brewing in my head a post about it, but I think I will omit most of it except to mention that it’s nice to finally see realistic depictions of computers in mainstream media. I will reserve the rest of my thoughts of the matter to myself. I got other more important things to blog about right now.

Octave documentation

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

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.

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.

A Personal Introduction to LiDIA

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

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?