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.
