LiDIA
Bill Hart
module is. Here are some notes:
* LiDIA does not compile with g++ version 4.1.2 let alone 4.2.2.
* The instructions on the LiDIA list for making it compile are
incomplete and seem to break various bits of the integer factorisation
code.
* I did get the LiDIA library to compile on a 2x Dual Core Opteron
Server running SUSE Linux with slight modifications to the
instructions for getting it to compile with later versions of gcc.
* "make examples" fails to build.
* "make install" misnames the LiDIA include directory
* The LiDIA interpreter lec is no longer supplied with LiDIA, the
authors had trouble building it themselves, so supplied precompiled
binaries, which are for a very old version of LiDIA and appear to be
inaccessible now anyway. It was last worked on at least 6 years before
LiDIA went stale.
* The first example program in the LiDIA manual does not compile
without modifications.
* LiDIA has still not been GPL'd after many months of promises.
* Contrary to my expectation, and as far as I can tell, LiDIA does not
have functions for computing the class group or fundamental units of a
number field, except possibly in the quadratic case (I didn't
check)!!
* I was able to generate a random polynomial over Z, define a number
field with a generator defined by that polynomial, then compute the
maximal order of that number field. Modulo the annoyance of
programming in C++, this was easy to do.
* LiDIA is about 2000 times slower than FLINT at multiplying two
length 20000 polynomials with 10 bit random coefficients.
* LiDIA does have various functions for working in orders of number
fields and for doing basic arithmetic with modules in number fields.
Bill.
John Cremona
days ago with Johannes Buchmann.
Buchmann's group created LiDIA about 15 years ago. At the time, the
fact that LiDIA would exist and be a C++ package was what concinved me
to convert all my old programs to C++ (from Algol68 if you're
interested). However I never used very much of what LiDIA provides,
and more recently relied on NTL more (so, for example, the mwrank code
in SAGE is compiled to use NTL and not LiDIA).
I asked JB specifically about GPL'ing LiDIA and he immediately agreed
saying there was no problem with that as far as he is concerned. He
said we should approach Christoph Ludwig who is the person currently
in charge of LiDIA. I guess that your aim is to get them to do this
and then to use whatever parts of LiDIA we need.
The LiDIA interactive interface never took off -- it was the pet
project of one person, who moved on.
Would the SAGE community like me to be the go-between here? I have
been in touch with Christoph Ludwig several times over the years
(though when I contribued elliptic curve code to LiDIA a long time
ago, that was before his time).
Meantime, Bill -- by default LiDIA compiles all of its packages, but
lots of them can be turned off by inserted suitable tags in the
configure command line. You could try that to see which parts were
broken.
John Cremona
--
John Cremona
William Stein
> I asked JB specifically about GPL'ing LiDIA and he immediately agreed
> saying there was no problem with that as far as he is concerned. He
> said we should approach Christoph Ludwig who is the person currently
> in charge of LiDIA. I guess that your aim is to get them to do this
> and then to use whatever parts of LiDIA we need.
Yes, exactly. If there is anything LiDIA can do better than NTL or Sage,
I would certainly like to know, and incorporate that code into Sage,
if possible.
> Would the SAGE community like me to be the go-between here? I have
> been in touch with Christoph Ludwig several times over the years
> (though when I contribued elliptic curve code to LiDIA a long time
> ago, that was before his time).
Yes, I think it would be great if you could get LiDIA GPL'd.
-- William
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
Bill Hart
If I recall correctly, William Stein already asked Christoph if a
GPL'd version of LiDIA was coming. His posts on the LiDIA list
indicate that Prof. Buchmann has agreed and that as far as he
(Christoph) is concerned, LiDIA is GPL'd. Christoph said he would
produce a GPL'd version of the code when he had time. But it has been
many, many months since he first promised to do this and a number of
people have asked since.
It does seem that the LiDIA copyright is owned by the LiDIA group, not
the individual authors (though these are credited in the individual
files after the general LiDIA group copyright notice is given). So
presumably Prof. Buchmann is the only person who needs to give
permission to GPL LiDIA. If he says to ask Christoph, and this has
been done, then all the permissions that are needed, have been given.
What is now needed is for someone to agree to add the GPL license
statement to every one of the hundreds of files in LiDIA and send a
copy to Christoph, who clearly doesn't have time to do this himself.
The source is available here:
ftp://ftp.informatik.tu-darmstadt.de/pub/TI/systems/LiDIA/current/
(I'm not suggesting you do that John, you are busier than all of us.)
Perhaps there is a program available which can do this automatically?
My suggestion would be to find a person willing to do the GPL'ing or a
program to do it automatically, and then have you, John, negotiate
with Christoph about making the new version available for download.
Clearly it should also be set up in some kind of svn or source
management repository. I think Christoph had also mentioned doing
that, but again has been too busy with Real Life TM and Real Job TM.
With regard to turning off various packages, this is not necessary. I
managed to get LiDIA itself to compile, just not the example
programs.
Also, LiDIA has a dependency tree that looks like this:
base
|
FF
|
LA
/ \
LT EC
| |
NF ECO
\ /
GEC
therefore switching off many of the modules is not desirable. The code
which is "broken" is the integer factorisation code, which has been
modified to allow LiDIA itself to compile, but external programs
linking against individual factoring algorithms such as p_minus_one or
pollard_rho will not work. The general factoring function which
chooses the algorithm for the user does work however, though it is not
clear to me if pollard_rho is ever called.
There could be a reason to use LiDIA for orders in number fields, but
with such ridiculously slow basic arithmetic, I don't see the point.
The algorithms for orders in number fields are not complicated
algorithms. The complicated algorithms for doing things like computing
class groups, seem to be missing from LiDIA.
On the elliptic curve side, it is clear that we don't need LiDIA since
SAGE already has mwrank, which is excellent!
I personally would like to see LiDIA GPL'd, but I'm struggling to find
anything in LiDIA which I'd really like to see used directly in SAGE.
But others may want to use it in SAGE, I don't know. One interesting
thing would be to have a SAGE interface to LiDIA, much as there is a
Magma interface, for example. Since the LiDIA interpreter is of no
use, this could make LiDIA useful again where it has not been to date.
Perhaps if it were GPL'd for this reason, there would be further
interest in developing LiDIA simply because it was easy to use from
within SAGE.
At any rate, if we just want to use the algorithms in LiDIA, do we
even care if it is GPL'd? The source is available to read and there is
nothing stopping us rewriting the algorithms contained therein. It's
neither illegal nor immoral.
BTW, I checked the LiDIA quadratic sieve and it is about 8 times
slower at factoring a 61 digit composite number than SAGE is via FLINT-
QS, i.e. about the same as Pari and a little slower than Magma.
Bill.
John Cremona
far.... but every little helps, and if Johannes remembers to ask
Christoph then he may be sprred into action.
As for physically GPL-ing the code, here's what I did for mwrank,
where admittedly the source code was not split into so many dir- and
subdirectories: I made a separate file containg the GPL info. I made
sure that every source file had basic identification in line 1 only,
followed by a coupld of blank lines; then a simple sed script
inserted the GPL text into every file after line 1. Done! I thnk the
same coud work with LiDIA source if combined with a find script to
apply this to every .cc and .h file there is.
I would behappy to do that -- but with all of us including JB onto
him, maybey CL will do it himself.
Either way, it sounds as if you (Bill) are the one with most LiDIA
expertise on the Sage team by now!
John
On 28/10/2007, Bill Hart <goodwi...@googlemail.com> wrote:
>
--
John Cremona
Bill Hart
On 28 Oct, 20:26, "John Cremona" <john.crem...@gmail.com> wrote:
> OK, so I wasn't trying to suggest that I was the first to have got as
> far.... but every little helps, and if Johannes remembers to ask
> Christoph then he may be sprred into action.
>
> As for physically GPL-ing the code, here's what I did for mwrank,
> where admittedly the source code was not split into so many dir- and
> subdirectories: I made a separate file containg the GPL info. I made
> sure that every source file had basic identification in line 1 only,
> followed by a coupld of blank lines; then a simple sed script
> inserted the GPL text into every file after line 1. Done! I thnk the
> same coud work with LiDIA source if combined with a find script to
> apply this to every .cc and .h file there is.
That sounds good. The individual tar.gz files for Lidia are in my home
directory on host-57-71 if you want to have a go. But in order to
maintain the integrity of LiDIA it would be necessary to unpack each
of the tar.gz files in turn and apply the script to the tree and
rearchive.
I'm not sure how svn can be used in a way that would keep each of the
modules of LiDIA separate but still allow one to check out all of
LiDIA in one go into a single directory tree. Do you know if cvs can
do this?
>
> I would behappy to do that -- but with all of us including JB onto
> him, maybey CL will do it himself.
Reading the LiDIA list it seems that Christoff has a few patches he's
got to merge as well. But we can probably do quite a lot with just the
GPL'ing done. Perhaps one of the things putting him off is that he has
so many things that need to be done to get it all into shape.
>
> Either way, it sounds as if you (Bill) are the one with most LiDIA
> expertise on the Sage team by now!
Ha ha! I've contributed precisely nothing to LiDIA. I contend that you
are the only expert here John!
Bill.
mabshoff
FYI:
[23:24] <rpw> I'll try to talk to christopher and JB about GPLing the
LiDIA code tomorrow.
[23:25] <rpw> I actuallys set up a subversion repo for LiDIA a couple
of weeks ago.
[23:25] <mabshoff> Jep, I figured you were the right guy to do that in
person :)
[23:25] <rpw> further details on sage-devel (ml) tomorrow morning.
[23:25] <mabshoff> mk
[23:25] <rpw> I'm to tired to type straight atm. I've been awake too
long.
[23:26] <rpw> see you guys in about 8 hours.
So you might want to wait a day for rpw.
Cheers,
Michael
John Cremona
which I will forward...
John
On 29/10/2007, mabshoff
--
John Cremona