On Oct 15, 2006, at 6:48 PM, Bill Hart wrote:
>> (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? Sometimes, to some extent. For example, at the recent workshop, we spent a long time working on optimising the SAGE GMP wrapper. (i.e. the Integer object in SAGE.) Basically what it comes down to is that an Integer object has to be a Python object to be visible to a SAGE user, and that's where the slowness comes from. So we were looking at how one can optimise construction of Python objects. Unfortunately, one finds for example that with a single-word mpz_add, only something like 5-10% of the time is currently in mpz_add. This is disappointing, and we're working on it, but we aren't going to get too close to what you can get calling directly from C. > 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. Heh I don't think of Python code as "scripts" any more. > 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. Absolutely there are limitations. As I said above, everything directly visible to the user needs to go via Python objects, and that's a fundamental bottleneck. On the other hand, there is nothing stopping us from writing C code in subroutines underneath. A good example is the work on exactly linear algebra being done at the moment. We're writing a bunch of generic python matrix classes, with specialised C versions (currently pyrex) for doing e.g. matrix arithmetic over Z/nZ for word-sized n. >> 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? It's complicated, and it's changing. Right now SAGE has a bunch of generic classes for dense and sparse polynomials over any (commutative) ring. So it can handle anything you throw at it, but slowly. On the other hand, if you create a polynomial over Z, it is represented internally by an NTL object, and arithmetic is done all using NTL. Still, the NTL wrapper sucks, and it's high on my list of priorities to fix. > 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. If you can write a library that's better than NTL, then SAGE will welcome it. Using a different "fundamental implementation strategy" to NTL is no problem, we're agnostic about that. (For example, it's a colossal pain to be changing the NTL modulus all the time, and SAGE buggers it up quite a bit at the moment.) Also, it would not be necessary to rewrite everything. SAGE uses all kinds of libraries in bits and pieces. For example, if you could duplicate the most important functionality in ZZ_X, then we could talk to that directly without using NTL for that at all. But this is a big project, it's not the kind of thing anyone can pull off overnight. Victor Shoup knows his stuff and has obviously put a lot of time into it. By the way, you mention gcd, extgcd, modinvert. I know there's work afoot to improve these things in GMP a lot. They're finally getting around to making gcd subquadratic, and for modular inverses there might be more mpn-level support for doing precomputations. David --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
