David Harvey wrote: > I should say in advance I don't completely understand where you're > coming from, but hopefully I can work that out over the next few > emails :-)
NTL was originally written when modern processors were not available and when GMP was not available (or not very good). As a result, NTL was built for something else entirely. Using NTL is basically using antiquated software, though I really, really appreciate what Victor has done for computational number theory, and I am not saying things that he doesn't know himself. My intention is to provide coverage of some of what is in NTL, and some of what is in Pari (another dinosaur), in a modernised library. It doesn't exist yet, and may never exist, so we are talking hypotheticals at this point. > > (1) > I hope you're aware that currently SAGE's NTL wrapper is pretty > hopeless. I mentioned this in one of my talks at Sage Days 2: I have no understanding of wrappers. I suppose that you could say that, currently, NTL seems to put some kind of "wrapper" on GMP, and I don't like it (though hats off to Victor for optimizing it pretty well notwithstanding). I'm afraid I have no insight into how wrappers work, so I'm not going to be able to help you optimize those. Can they even be optimized? SAGE is written in Python right? And you are calling C functions from within Python scripts. But some of this is difficult to do by hand, so you are using Pyrex to do it for you. That's my current level of understanding of the matter, and no, I have never heard of Pyrex before I met SAGE and don't program in Python. I can't say I am a fan of bundling functions together with Python scripts whichever way it is done. But SAGE pretty much has to do that, as there is no package which offers everything. I understand that. But this means there will be *some* limitations to what SAGE can offer if I am not mistaken. > > http://sage.math.washington.edu/home/dmharvey/padic-heights-talk.pdf > > (specifically the slide titled "Problems with NTL interface") > > These problems make NTL's functionality not very useful from a SAGE > user's point of view, if they actually want to do any real > calculations. I am planning to fix these problems, but first I need > to do some work on SAGE's polynomial and polynomial ring classes, so > it will take a little time. When you say SAGE's polynomial classes, etc, what is actually doing the grunt work there? SAGE? I mean have you written algorithms in Python? Or are you wrapping some other package, such as NTL or Pari? > > (2) > I think it's wonderful that you're beating NTL. On the other hand, > NTL is a big, mature library. To the extent that your code can > actually replace the stuff in the NTL library, you might consider > contributing your code to NTL itself. I've discussed a few > improvements relating to polynomial multiplication with Victor Shoup, > he seems quite receptive to new ideas and code, and there are plenty > of examples in the code where he gives attribution to other people. > He doesn't exactly have a blazingly fast release schedule, but in the > long run that might be a good option. I may end up just using it myself and not contributing it anywhere in particular. If a rewrite of NTL can be of use in SAGE somehow, then all well and good. If not, then that doesn't matter. I am sure there is plenty more I can contribute to SAGE. I don't plan to contribute directly to NTL at present. Although I *could* speed up some of the algorithms within the context of NTL itself (gcd, extgcd, modinvert, CRT so far seem to be the biggest winners there), that would only be piecemeal optimization. The real advantages in runtime come from changing the fundamental implementation strategy of NTL itself (something Victor no doubt would have strong opinions about). That means a rewrite from the ground up, though obviously the further you get from GMP basic types, the more the library begins to look like NTL and become compatible with it. What I had in mind was a dictionary for converting any NTL function call to a call to my library. You could almost get away with replacing all instances of ZZ, QQ and RR with appropriate GMP types in any NTL compatible code, and then using a whole pile of #defines to convert calls to NTL functions to calls to another equivalent library (such as mine) based on the fundamental GMP types. Absolutely no overhead at all would incurred in doing this. You'd get the full benefit of the optimized library and the whole process of converting NTL compatible code to the alternative form could be pretty much automated. If a new function is added to NTL, one would simply need to implent it in the new library and add it to the dictionary. If I can make something like that work, I'll implement it and offer it to SAGE as a drop in replacement for NTL. But it obviously isn't going to happen overnight. > > (3) > The main stuff we're interested in (or at least, the main stuff I am > interested in) from NTL is the following: > * ZZ_X > * ZZ_pX > * finite fields and polynomials over them > * Possibly zz_x, zz_pX Currently I'm working towards an algebraic number theory package sitting on an optimized rewrite of NTL. The packages you mention are not high on my list of current priorities though, except for the polynomials over ZZ. I don't have any really good ideas there yet though apart from the usual CS type of optimizations. > > Do you think the kind of things you are doing to beat NTL are going > to be able to beat its implementation of these things too? Of course, most of the speedups I use in code are general speedups for modern processors, and apply to almost any kind of code. Algorithms on the other hand take time to develop and happen by chance, though I am a number theorist, so anything is possible. > > I'm not that interested in the matrix classes. Also I'm not > interested in wrapping NTL's ZZ class. (We do have a wrapper > currently, but it's only there for completeness since we have a > wrapper for ZZ_X, but really there's no need to have it.) Yes, of course ZZ doesn't offer very much, but some of NTL's other classes use ZZ. So if ZZ is not optimized, the latter packages aren't either. I wouldn't like to see ZZ wrapped. It performs very few functions whose runtime wouldn't be dominated by the overheads in the wrapper. I presume you wrap Pari for that type of stuff, along with some Python algorithms for small int stuff. The only way to wrap something like NTL ZZ would be to write an interface to NTL in C, which can handle multiple requests at once, or something like that. But I think it would be a disaster. I personally wouldn't try, and I think there are distinct benefits in not doing so, especially if an NTL equivalent library does emerge. > > David Bill. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com 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/ -~----------~----~----~----~------~----~------~--~---
