I looked at LiDIA a long time ago (like 1999 or 2000) and I remember being very impressed both with its scope and with its modular (i.e. recursive) data types and programming dogma. However, I decided against using it simply because of its license. I suspect that other developers may have made the same decisions and that is why LiDIA isn't widely used. If it were GPL'd, then I would certainly find it extremely useful.
Although Bill is correct in that LiDIA will never be as fast as from-scratch implementations like FLINT, the advantage of recursive data types is that you get a lot of code re-use with minimal effort. Since it's done with a nice object oriented interface, you can change the implementation at almost any level without having to worry about propagating changes manually though the code. LiDIA in GPL'd form would also be very useful to me personally because LinBox already has hooks built in to use LiDIA... so any data structure (i.e. Number Fields...) added to LiDIA get propagated into LinBox with minimal effort. However, before I spend any time writing code for LiDIA, I want to see it released under GPL. --jason On 4/23/07, Bill Hart <[EMAIL PROTECTED]> wrote: > > It would be very valuable if LiDIA were GPL'd! I re-skimread the > entire 700+ page manual last night. > > I'm not certain how many people actually use LiDIA, but my guess is > not that many. And I really don't know why this is. It is very well > documented (if not a little too verbosely, and without sufficiently > many examples), has a wide coverage and is actually structured very > well. It is a particular shame that it is not widely used given the > amount of man years that has gone into the project. > > My feeling is that it lies between two paradigms. It is neither a > minimalist superfast C library, nor is it a computer algebra system > with a nice front end (or at least I don't know of one). So it won't > get used like the Pari/GP package because of the lack of front end, > and it wouldn't be my choice if I wanted the greatest possible speed > if I were writing a C program. For one thing it is not necessarily > easy to tell which parts of the library are going to be superfast and > which are going to use generic routines. > > However, as far as I can tell, all LiDIA types are recursive on > account of the generic programming used and everything but p-adics > seems to be there. It has memory management, error handling and signal > handling. > > It is even possible to do some things quite fast. I realised last > night that one could use the polynomials over prime fields to > implement fast polynomial mutiplication if one so desired. Victor > Schoup seems to have been involved too, so perhaps the specialised > polynomials over bigints allow for asymptotically fast polynomial > multiplication, which I imagine is on par with NTL (though I haven't > checked this). My impression had been that only the naieve polynomial > multiplication routine had been implemented, but I think I was looking > at the generic routine not the specialised polynomials over bigints > routine. > > There are various factoring routines available, including (if you look > in the right place) p-1, p+1, ECM, MPQS and others. However, I > understand that some of the Pari routines are souped up versions of > these (e.g. the quadratic sieve in Pari came from LiDIA), so I don't > expect them to be dazzlingly fast. > > The algebraic number theory package seems to contain quite a bit of > stuff. There's binary quadratic forms, quadratic number fields, > general number fields, even factorization into ideals and routines for > working with ideals and elements of number fields. It doesn't have as > much as Pari, and it is all restricted to absolute extensions of Q as > far as I can tell, but it doesn't look too bad. > > The elliptic curve package has quite a lot of stuff in it, even down > to implementation of computing Siksek bounds I think. It also has > stuff for crypto, point counting, generating curves using complex > multiplication, etc. I'm not sure I'd go so far as to say it contains > the best implementations of elliptic curve stuff anywhere, but it > certainly does contain quite a bit of good stuff. I see Nigel Smart, > John Cremona and others have contributed code. > > It doesn't have any p-adic routines obviously, and there aren't > routines for converting from cubics of genus 1 to Weierstrass elliptic > curves, I don't think. > > There doesn't seem to be a way of resurrecting LiDIA by replacing all > the basic arithmetic code in it with faster stuff. One can replace the > kernel with a custom kernel, as far as I can see, but this just > wouldn't cut it. One would need to replace the entire bigint package, > and all the other basic packages it sits on (doubles, complex > arithmetic, reals, rationals, etc). But once one did that, everything > else on top would run faster automatically because of the way it's > written. But I'm not personally enamoured of recursive data types. > There is almost always a way of doing something quicker by > implementing it from scratch rather than implementing a high level > routine which works for various underlying data types. > > In summary, from the point of view of the FLINT developers, LiDIA is > only useful for picking to pieces (should it be GPL'd) to see how > things are done and to get lots of good ideas. But it could be quite a > bit more useful for SAGE. Because there are specialised versions of > routines for some things, it probably does run quite fast for many > things, and it is certainly conveniently constructed and extremely > well documented. > > In many parts of LiDIA, the only things implemented are basic > arithmetic operations, square roots, powers, power mods, and that is > about it. In some ways that is natural if you are defining operations > which must work for all basic LiDIA types and even for recursive > types. But even in the more specialised parts of LiDIA, one can > imagine many other routines implemented on top of the basic LiDIA > stuff. > > Bill. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
