------- Forwarded message ------- From: "William Hart" <[EMAIL PROTECTED]> To: "William Stein" <[EMAIL PROTECTED]> Cc: Subject: Re: Fwd: NTL speed test Date: Sat, 14 Oct 2006 18:26:47 -0700 William, Err, um, you can post that if you want. But I modified it to read a bit better, in case Victor reads it, and also to correct some things that I didn't say very well. As for reimplementing NTL, it is already basically on top of GMP. It just misses out on some of the power of GMP by being originally written to sit on top of another package, since GMP wasn't available at the time. By writing a similar package to NTL, but essentially different, one can harness the full power of GMP. Some of the algorithms Victor uses are also not quite optimal. At least not on my architecture they are not. So there is more to it than just transferring the existing code over to GMP. Some of it needs rewriting from scratch. His compromise of writing NTL based on the mpn functions in GMP, instead of the higher level mpz functions, does save him some time, but apparently not quite enough. Bill. --- William Stein <[EMAIL PROTECTED]> wrote: > Bill, > > Could I post the following to the sage-devel > list? > > -- William > > Hi Everybody, > > Any comments on this. William Hart is a > super-energetic > skilled programmer, who is 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. __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
