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

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?

Leave a Reply

Your email address will not be published. Required fields are marked *