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/ -~----------~----~----~----~------~----~------~--~---
