Hi all, Apologies if this appears twice, but google groups seems to have lost the original posting.
William Stein suggested I join the group and post something I emailed to him, for comments from the sage-devel list. I see he has already posted a link to the quadratic sieve I wrote for SAGE (around 3 times faster than the current SAGE/Pari one, I think): http://www.friedspace.com/QS So on to the current matter.... Here is a copy of my correspondence with William re NTL. Please see his question to the group (sorry for the backwards quoting - apparently William replied to my email before I sent it to him - he works faster than the speed of light ;-) ): >> Hi Everybody, >> >> Any comments on this. William Hart is a >> super-energetic >> skilled programmer, who seems to be suddenly >> obsessed with >> re-implementing certain of the functionality of NTL >> as a C library >> on top of GMP. Any advice, thoughts, comments, >> etc., for him? >> He would make the results GPL'd and include them in >> SAGE. He >> is doing this 100% because he wants optimal >> performance -- see below. >> > ------- Forwarded message ------- > From: "William Hart" <[EMAIL PROTECTED]> > To: "William Stein" <[EMAIL PROTECTED]> > Cc: > Subject: NTL speed test > Date: Sat, 14 Oct 2006 17:23:40 -0700 > > Hi William, > I decided to see just how much of an overhead there > is using NTL as opposed to something written > specifically *for* GMP. > > So over the weekend I wrote my own library (some of it > from code I already had lying around) of a selection > of functions similar to those in NTL's ZZ library > (which end up mimicing pretty much everything NTL does > in ZZ that GMP doesn't already do). > In comparing the times, I compared my code with NTL > compiled on top of GMP and tuned with Victor's script. > The result is that everything I implemented was > between 1.33 and 2.2 times faster than NTL (including > the stuff that doesn't rely on GMP at all - I just use > slightly better algorithms and save some time not > doing bounds checking in time critical functions). > > As I suspected, there is quite a lot of loss in > building one package on top of another that it wasn't > originally written to sit on top of, as NTL does. > > I also implemented a square root mod p^k function, > which NTL doesn't have (I don't think). > > Anyhow, I attach the library to this email, though > note that this library is *NOT* a drop in > replacement for Victor's ZZ library (something I am > sure Victor thought of writing when GMP came along, > his current product essentially being the compromise). > > > The point of the implementation I give is to expose > the underlying GMP types and allow one to work > directly with GMP functions where available. > > I'll work on a replacement for his vec_ZZ (very small) > and mat_ZZ (more involved) libraries next. I have some > ideas for how to speed those up a LOT, especially in > terms of making use of processor caches, etc!! > > I'm not sure how much of NTL I need to implement > before I can implement algebraic number theory stuff. > But I get the impression it isn't that much. > Regards, > > Bill Hart. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
