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.
