Thank you Bill. Regards.
On Mon, Sep 23, 2013 at 12:13 AM, Bill Hart <goodwillh...@googlemail.com> wrote: > 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. -- 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.
