Sorry, "multiprecision word" should have read "multiprecision (multiword) integer" of course.
Bill. On 22 September 2013 22:12, Bill Hart <goodwillh...@googlemail.com> wrote: > mpn_mod_1 only computes remainder after division by a single word, whereas > mpn_tdiv_qr computes remainder after division by a multiprecision word. > > However, as implemented, mpn_mod_1 does not compute the quotient, only the > remainder. It uses a fantastic algorithm due to Montgomery. Thus it is very > fast. > > Bill. > > > On 22 September 2013 21:58, mgundes <mg...@hotmail.com> wrote: > >> Thanks Bill, really appreciated your brief answer. >> >> I have one more question. I need the quotient so that I use >> mpn_tdiv_qr. However when I replace mpn_tdiv_qr() with mpn_mod_1() >> it is too much faster about 2-3 times. mpn_mod_1() returns remineder >> which means it also can calculate quotient too, right? Then why it is >> that faster than mpn_tdiv_qr()? Any idea? >> >> Thanks, >> Regards. >> >> >> On Sun, Sep 22, 2013 at 11:28 PM, Bill Hart <goodwillh...@googlemail.com> >> wrote: >> > Yes, there's a few things you can do to speed it up. >> > >> > * You don't need to memset to 0. The mpn_tdiv_qr function writes over >> what >> > is there (I hope). >> > >> > * The latest trunk branch in my git repo has slightly faster division >> code >> > (10-20%) over a good range. >> > >> > * If you are reducing many values by the same modulus, you would be >> better >> > to compute a precomputed inverse and multiply by it, instead of doing a >> > division. See [1] for a good algorithm. Also see [2] and [3] for >> > implementations of division with precomputed inverse. Look in the test >> > subdirectory there to see examples of use. I don't promise that this is >> the >> > best way to do things, and I don't recall which implementation is >> faster. >> > >> > * You may get some ideas from Modern Computer Arithmetic [4] >> > >> > * You may also want to look at Montgomery's REDC algorithm, depending on >> > your application. >> > >> > A lot depends on your precise application and how big the operands are. >> > >> > Speeding this sort of thing up is an active area of research, so there >> are >> > many, many possibilities out there. >> > >> > Bill. >> > >> > [1] http://gmplib.org/~tege/division-paper.pdf >> > >> > [2] >> https://github.com/wbhart/flint2/blob/trunk/mpn_extras/mulmod_preinv1.c >> > >> > [3] >> https://github.com/wbhart/flint2/blob/trunk/mpn_extras/mulmod_preinvn.c >> > >> > [4] http://www.loria.fr/~zimmerma/mca/pub226.html >> > >> > >> > On 22 September 2013 21:08, mgundes <mg...@hotmail.com> wrote: >> >> >> >> Hello everyone, >> >> >> >> I am trying to do "a*b mod n" operation with big numbers. I have >> >> written a function which is working fine but I am wondering if I can >> >> make it faster. >> >> >> >> Do you have any advice about speed up function below? >> >> Thanks a lot, >> >> Regards. >> >> >> >> >> >> /* >> >> "(a * b) mod p" operation with mpir functions >> >> */ >> >> void MpirMultiplyModReduct(const mp_limb_t *a, const mp_limb_t *b, >> >> mp_size_t size, const mp_limb_t *mod) >> >> { >> >> mp_limb_t multiplicationResult[size*2]; >> >> memset(multiplicationResult, 0, size*2 * sizeof(mp_limb_t)); >> >> >> >> mp_limb_t c[size]; >> >> memset(c, 0, size * sizeof(mp_limb_t)); >> >> >> >> mp_limb_t d[size]; >> >> memset(d, 0, size * sizeof(mp_limb_t)); >> >> >> >> mpn_mul(multiplicationResult, a, size, b, size); >> >> mpn_tdiv_qr(c, d, 0, multiplicationResult, 2*size, mod, size); >> >> } >> >> >> >> >> >> >> >> -- >> >> MahmutG >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups >> >> "mpir-devel" group. >> >> To unsubscribe from this group and stop receiving emails from it, send >> an >> >> email to mpir-devel+unsubscr...@googlegroups.com. >> >> To post to this group, send email to mpir-devel@googlegroups.com. >> >> Visit this group at http://groups.google.com/group/mpir-devel. >> >> For more options, visit https://groups.google.com/groups/opt_out. >> > >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups >> > "mpir-devel" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an >> > email to mpir-devel+unsubscr...@googlegroups.com. >> > To post to this group, send email to mpir-devel@googlegroups.com. >> > Visit this group at http://groups.google.com/group/mpir-devel. >> > For more options, visit https://groups.google.com/groups/opt_out. >> >> >> >> -- >> MahmutG >> >> -- >> You received this message because you are subscribed to the Google Groups >> "mpir-devel" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to mpir-devel+unsubscr...@googlegroups.com. >> To post to this group, send email to mpir-devel@googlegroups.com. >> Visit this group at http://groups.google.com/group/mpir-devel. >> For more options, visit https://groups.google.com/groups/opt_out. >> > > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to mpir-devel+unsubscr...@googlegroups.com. To post to this group, send email to mpir-devel@googlegroups.com. Visit this group at http://groups.google.com/group/mpir-devel. For more options, visit https://groups.google.com/groups/opt_out.
