I don't know if there is a version of mpn_mulmod_2expm1 in GMP 5 or not though. Does their p1 version allow negative values for n? I didn't check.
Bill. 2010/1/11 Bill Hart <goodwillh...@googlemail.com>: > Hey, the GMP 5 library now has a version of our mpn_mulmod_2expp1. > It's also undocumented I believe, but we can now use it in our timing. > That should give GMP a good speedup for this. > > When this test was written, such a function did not exist in GMP. > > The GMP 5 library is just a few days old. Give us a chance to catch up! > > Bill. > > 2010/1/10 Gianrico Fini <gianrico.f...@gmail.com>: >> It didn't took me so much time as I feared to understand why the use >> of bench_two on GMP4.3 and MPIR1.3 (on my 32-bit CPU) gave so strange >> results... >> GMP4.3 was (slightly) faster than MPIR1.3 for all tests, expect two >> where it was terribly slower: fermat and mersenne. The overall score >> says: >> >> GMP4.3 => 136, 97.2 >> MPIR1.3 => 145, 104 >> >> I.e. the bench_two test I downloaded from mpir.org says that yes, for >> many application GMP is faster, but there are some (two) where it is >> by far slower... so, globally, MPIR is 6% better than GMP. >> >> It sounds strange, doesn't it? >> >> Well, go and look into the code, the tarball is available from the >> main page of MPIR, you can download it, unpack it and... before you >> use it, please READ THE CODE! >> >> The two very interesting test files are: fermat_prime_p.c, >> mersenne_prime_p.c . >> >> Let's start from the first one: fermat_prime_p.c >> >> At the beginning you can find: >> #ifndef __MPIR_VERSION >> // we are gmp >> #define NEED_MULMOD >> #elif __MPIR_VERSION < 1 || (__MPIR_VERSION == 1 && >> __MPIR_VERSION_MINOR < 3) >> #define NEED_MULMOD >> #endif >> >> ...you will see, this means: if someone is testing GMP or a version of >> MPIR before 1.3, be _as_slow_as_possible_. The reason? This way MPIR >> will look like being fast :-D >> >> The "application" is very simple, it performs a "Pepin's Test for k" >> i.e. test if "3^((F_k-1)/2) == -1 mod F_k", where "F_k = 2^(2^k)+1". >> >> How would you write such an application? You would probably think you >> can use the documented function mpz_powm... >> The test doesn't do this, because this could be fast on libraries >> different from MPIR-1.3, and the goal is to be _slow_... so it will >> use a loop and the _undocumented_ function mpn_mulmod_2expp1. This is >> a test to see how the library perform with a typical application, and >> uses a function that NO application will use, for the simple fact that >> _it_is_NOT_documented! >> You can try: >> mpir-1.3.0$ grep -ri mulmod doc/mpir.* >> >> Nothing, no answer, it is not documented at all...And if you are not >> using MPIR-1.3? will the test use something different? NO! It will >> perform the computation using an _as_slow_as_possible_ substitute for >> that function. >> >> NO APPLICATION WILL EVER BE SO CRAZY, THIS IS NOT AN APPLICATION, IT'S >> A FAKE!!! >> >> I'll not analyse the ridicule "substitute", I'll do for the next >> "application", because it is absurd exactly in the same way! >> >> Next application: mersenne_prime_p.c >> Here the "application" uses the Lucas-Lehmer test on a Mersenne >> number, now the loop make sense, because it is not a simple >> exponentiation, but a sequence of squaring-subtract, to be performed >> modulo 2^p-1. >> How would you implement it? With some clever reduction using mpn_add_n >> or initialising the modulo once and then using it again and again... >> >> But here, again, the main goal of the person who wrote this code was >> to show that his mulmod function was giving a tremendous speed up, so, >> again, the fake-application uses an undocumented function. Let us look >> at the line where it is used: >> mpn_mulmod_2expm1 (rp, xp, xp, k, tp); // mpn_sqrmod_2expm1 would be >> faster >> Note the comment, using sqr can be faster! Then read the fake, >> as_slow_as_possible, implementation that is used if you are measuring >> speed of something different wrt MPIR-1.3: >> >> void mpn_mulmod_2expm1 (mp_ptr xp,mp_ptr yp,mp_ptr zp,mp_size_t >> k2,mp_ptr tp) >> {mpz_t x,y,z,m;mp_size_t n,tn; >> n=BITS_TO_LIMBS(k2); >> mpz_init2(y,k2);mpz_init2(z,k2);mpz_init2(m,k2);mpz_init2(x,2*k2); >> mpz_set_ui(m,1);mpz_mul_2exp(m,m,k2);mpz_sub_ui(m,m,1); >> MPN_COPY(y->_mp_d,yp,n);tn=n;MPN_NORMALIZE(y->_mp_d,tn);y- >>>_mp_size=tn; >> MPN_COPY(z->_mp_d,zp,n);tn=n;MPN_NORMALIZE(z->_mp_d,tn);z- >>>_mp_size=tn; >> mpz_mul(x,y,z); >> mpz_mod(x,x,m);tn=x->_mp_size;if(tn>n)tn=n; >> MPN_COPY(xp,x->_mp_d,tn);if(tn<n)MPN_ZERO(xp+tn,n-tn); >> mpz_clear(x);mpz_clear(y);mpz_clear(z);mpz_clear(m); >> return;} >> >> The guy who wrote this fake application decided to implement the >> needed sqrmod with the slowest possible strategy. Directly using mpn? >> no, there is the risk to be fast: >> - let's allocate four mpz on the fly (this means for every iteration!) >> - let's recompute the modulus in mpz on the fly (it is constant for >> the full run and it is recomputed every iteration!!!) >> we should exploit the fact that this function will always be called >> with yp==zp, but again we run the risk to be efficient, and the author >> did NON want that, because this function is used for other libraries, >> to be compared with MPIR... and they must be slowed down! So, you >> perfectly know (read the comment above) that yp==zp, but >> - copy the memory _twice_ in _two_different_ new locations... >> This way mpz_mul will see two different pointers and will _NOT_ use >> sqr! Clever way to avoid any possibly faster primitive!!! >> - copy back the result (the third copy, to be repeated for any cycle!) >> - free the memory...(for the same variables that will be used >> [recreated] again in the next step). >> >> It is quite obvious, if you read the code of this two functions that >> it was written with one goal in mind, show that any library without >> those two functions was slow... or, to be more exact, that any other >> library (i.e. not MPIR-1.3) was slow. >> >> BUT THIS IS A FAKE! >> >> As a conclusion, on my laptop, MPIR is able to be faster than GMP >> !!!!!!!!ONLY CHEATING!!!!!!! >> >> You guys are very funny!!!! :-D >> Because the cheating is so evident that when your library is slower on >> all operation, the fake application is 3-4 times faster with your >> funny-library... and your benchmark is so.... ingenuous .... to >> conclude that overall the funny-fake-library is faster!!!! >> RIDICULOUS!!!!! >> >> But now be serious, and confess... MPIR is not a library, it's a >> joke! :-D >> >> AH AH AH AH!!!! >> Adios! >> >> Gian. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "mpir-devel" group. >> To post to this group, send email to mpir-de...@googlegroups.com. >> To unsubscribe from this group, send email to >> mpir-devel+unsubscr...@googlegroups.com. >> 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 mpir-de...@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.