Ah, what the hell, let's look at the list and see what we have and don't have yet. No one'll really read this anyway....
Bugs : none - yeah we don't ever have those either. :-P 1) Same size large multiplication : new Toom functions (what we would call mpn_toom8_mul_n and mpn_toom8_mul ??). We have toom7 which will be a few percent slower, one presumes - though we've had it for ages and are about to move on to the next big thing. 2) mpn_mulmod_bnm1 (for A*C mod (B^n-1)). We have this function, and similarly one for mpn_mulmod_bnp1. However they currently do nothing interesting. I recall Jason Moxham saying he had some code for both of these, but I haven't seen it yet. I have some code for the p1 case when n is divisible by 3, which I will be using in my FFT code. 3) Squaring. Yeah we have toom7 for squaring. I will implement the bnm1 and bnp1 squaring when I finish the FFT. It's not complicated and has to be done anyway. 4) Many new Toom functions for smoothing the multiplication times of unbalanced operands. We have a fair few functions for this, but we've not gone as crazy as they have!! As I've mentioned before, I believe we are going to do away with Karatsuba and Toom altogether shortly, replacing it with something better, so no point us implementing all these functions. It's great their times are so smooth though. A *lot* of work must've gone into this. 5) Schoolbook division uses faster quotient approximation. Hmm. I am really surprised this is faster. Jason wants to do schoolbook in assembly. This one is a puzzle to me. I mean, I implemented a quotient approximation version of schoolbook, which we have, but I just didn't notice if it was faster. I never timed it. 6) Asympotically fast division, in time O(M(n)). We definitely don't have this and it is completely nontrivial. But this will be a major milestone on our long march obviously and much of what we've been doing is gearing up for it. 7) Quotient only division is O(M(q)) on average. We have that trick (up to not having asymptotically fast division). I implemented it ages ago. 8) REDC ops now O(M(n)). I didn't know it was part of the public interface, and I've no idea what we do for REDC. We should check into this. 9) Exact division faster, time O(M(n)). Again, no asymptotically fast division for us yet. I don't know where we currently stand for the non-asymptotically fast stuff. This one we need benchmarks for. 10 mpz_powm speedups. No, we have not worked on this at all. These sound like nice tricks. 11) Mulders' algorithm for mullo. I believe Jason sped ours up, so I think we have this already. (Something similar for mulhi?). 12) Inverse computation. This is really part of the division stuff. We have the asymptotically fast wraparound stuff for approximate inverses, but not the mod_bnm1 stuff. 13) mpz_perfect_power_p asymptotically faster. They don't list the algorithm, so I can't compare. But we had already sped this up. From memory our cube root code sucked though. 14) mpz_remove improvements. I don't think we've touched it yet. We still aren't sure of our primality interface, so this needs more thought on our part. 15) Intel Atom and VIA Nano. We support both but only have actual optimisations for the former, I believe. Of course there's plenty more where that came from. 16) Hundreds of other bits and pieces. Yes, we have that. :-P 17) mpz_powm_sec side-channel gizmo. No plans for this in MPIR. 18) mpn_sqr. Trivial to add this. 19) mpn_and_n, mpn_ior_n, mpn_xor_n, mpn_nand_n, mpn_nior_n, mpn_xnor_n, mpn_andn_n, mpn_iorn_n, mpn_com, mpn_neg, mpn_copyi, mpn_copyd, mpn_zero. We have had all these for ages. 20) mpn_tdiv_qr allows some aliasing. We've been aliasing ours for a long time. Should we have not done so? 21) Fat binaries for 64-bit x86 processors. I think we've had that from version 0.9 or 1.0 or something like that. 22) mp_bitcnt_t for bit counts. Great idea. I support this. It's a single #define, but means going through MPIR and actually using it. Doesn't actually do anything for you, but if people want something nice and portable, C is not that something. Introducing nice portable types like this is a great idea. 23) Support for Win64. Hysterical laugh. I expect GMP to not be a GNU project for much longer. RMS will write to them and tell them that "The most minimal support for the free software movement is to refrain from going directly against it; that is, to avoid presenting proprietary software as legitimate" as he reportedly did with the GNOME project. 24) xgcd normalisation - for smaller operands I believe we normalise as they do, but I've not checked that we do so for large operands. No one noticed anyhow cause most people test xgcd(2, 3) in their test suites and that's about it (exaggeration). Not sure the MPIR test suite ever demanded any particular normalisation, nor the docs. We should probably tighten this up, lest someone be misled. 25) Use mpn_sqr for squaring. Fair enough. 26) Lots of new tuning thresholds. Yeah we could do with more. We have been adding them, but probably not enough of them. 27) tune/speed works with many new functions. We have virtually all mpn functions in tune/speed these days and have made radical improvements to the flexibility of the latter program. 28) Remove mpn_bdivmod. Irrelevant for us. Didn't like it anyway. 29) Better testing. Jason started doing some things, such as making random functions more... well, random, and some other changes, but I would believe their test suite has many other improvements. I hope I am not being too flippant above. In many cases where we can say, "we have that already", they probably have it optimised better than us. I am not trying to take anything away from the large amount of effort those guys put in. I am sure they are well ahead of us on many things at present and that we have some catching up to do. Also, they've got their new release out, and ours is still in the workshop! We also have a quiet period of 2-3 months coming up where little MPIR work will get done. Around July we'll have a big explosion of effort mehopes. Bill. 2010/1/9 Bill Hart <[email protected]>: > Oh, it has definitely changed. Not all of the things they've been > working on have made it in, so in some sense they are actually being > modest about what they've been working on. But what has been released > is already quite a lot. > > Their strategy of releasing a more bleeding edge version of GMP and an > older more stable version is quite a good one too, in my opinion. > > Really, the fact that they now have asymptotically fast division, > after all this time, is quite an achievement. We should congratulate > them. They've also cleaned up the division so that if the quotient is > very small then the time approximately depends on the size of the > quotient. We basically have the latter in 1.3, but certainly not the > former. > > They also worked on Toom 8. I didn't actually look to see if that is > used, but their release notes would suggest it probably is. Again, > that is a non-trivial achievement. > > Bill. > > 2010/1/9 Jeff Gilchrist <[email protected]>: >> On Sat, Jan 9, 2010 at 6:35 AM, Cactus <[email protected]> wrote: >>> Now that GMP 5 has been released, we will have to make a decision on >>> whether to make changes to MPIR or ive up GMP compatibility. An >>> outline of the features in GMP 5 is given here: >> >> I didn't even notice that it has been released. Has anyone run any >> benchmarks yet to see if anything has really changed? >> >> Jeff. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "mpir-devel" group. >> 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/mpir-devel?hl=en. >> >> >> >> >
-- You received this message because you are subscribed to the Google Groups "mpir-devel" group. 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/mpir-devel?hl=en.
