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.
