On Sunday 15 February 2009 21:02:11 Bill Hart wrote: > On the right hand side of the first page of Granlund/Montgomery some > references are given to doing division by multiplying by divisors of > 2^k-1 (for small k). I guess this is the closest thing. > > Rereading our correspondence on this issue has been useful. You > pointed out Theorem 4.2 of this paper at the time, and recently I had > been looking for a statement of such a theorem, but had not been able > to find it. It's a very useful theorem. > > Bill. > > 2009/2/15 David Harvey <dmhar...@cims.nyu.edu>: > > I'm pretty sure the division by B-1 algorithm itself is not new, I > > think Quercia's numerix library had it some time ago, from memory he > > used something basically equivalent to calling mpn_add_n with > > overlapping source and destination buffers (very sneaky). Also I > > believe Zimmerman + Bodrato + Zanoni independently came up with that > > idea (or something similar). I'm only claiming credit for the idea of > > combining it with multiplication to get fast division by divisors of > > B-1. I wouldn't be terribly surprised if that had been done before as > > well, but I don't know of any instances --- let me know if you find > > any. I also am not claiming credit for figuring out a good assembly > > implementation of this --- it looks like at least one MPIR developer > > has figured this out, and I know Torbjorn has done so as well on > > several chips (but I have not gone through the pain of trying to > > understand how his code works). > > > > david > > > > On Feb 15, 3:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > >> OK, I checked and the discussion about this paper was related to > >> something else. Sorry for the confusion. So it was indeed you that > >> came up with the divide by B-1 idea. > >> > >> Bill. > >> > >> 2009/2/15 Bill Hart <goodwillh...@googlemail.com>: > >> > I'm talking about that paper. > >> > > >> > I don't recall when we discussed this paper, but I recall you asking > >> > me "have you read this paper" at some point, and my memory of it was > >> > that you considered something we were discussing as essentially being > >> > present in there. Sorry if I have conflated two different issues here. > >> > > >> > If you say so, then I'm happy to credit Harvey, Hart, Gladman, Moxham. > >> > > >> > Bill. > >> > > >> > 2009/2/15 David Harvey <dmhar...@cims.nyu.edu>: > >> >> On Feb 15, 2:34 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > >> >>> At some point we discussed where the original, original idea came > >> >>> from. At some point you read Granlund-Montgomery (after we had our > >> >>> discussion, I think) and at some point you may have decided that the > >> >>> idea was essentially already present in that work. > >> >> > >> >> I'm sorry Bill, I have no idea what you are talking about. Are you > >> >> talking about "division by invariant integers using > >> >> multiplication" (1994)? What does that paper have to do with this? > >> >> That would be rather odd, as GMP would have had this algorithm years > >> >> ago if Torbjorn had known about it. > >> >> > >> >> david > > I've put the new mpn_divexact_by3 in the k8-branch with a new generic C version so you can see how it works. This version is a direct replacement for the old mpn_divexact_by3 , by paying closer attention to the exact form of the carry-in/out .
I've done the k8-branch merge locally , and I'm just waiting for the windows bits before I can commit to svn. mpir/branches/K8-experimental# svn status mpir/branches/K8-experimental# svn update At revision 1614. mpir/branches/K8-experimental# cd ../../trunk/ mpir/trunk# svn status mpir/trunk# svn update At revision 1614. mpir/trunk# svn merge -r 1499:1614 ../branches/K8-experimental/ C Makefile.in U mpn/Makefile.in C mpn/x86_64w/amd64/aorsmul_1.asm U mpn/x86_64w/amd64/gmp-mparam.h A mpn/x86_64w/amd64/diveby3.asm A mpn/x86_64w/amd64/lshift1.asm A mpn/x86_64w/amd64/sumdiff_n.asm C mpn/x86_64w/amd64/mul_1.asm A mpn/x86_64w/amd64/addadd_n.asm A mpn/x86_64w/amd64/addsub_n.asm A mpn/x86_64w/amd64/rshift1.asm A mpn/x86_64w/amd64/aors_n.asm C mpn/x86_64w/amd64/mul_basecase.asm A mpn/x86_64w/amd64/lshift.asm C mpn/x86_64w/amd64/sqr_basecase.asm A mpn/x86_64w/amd64/com_n.asm A mpn/x86_64w/amd64/addlsh1_n.asm A mpn/x86_64w/amd64/sublsh1_n.asm A mpn/x86_64w/amd64/rshift.asm D mpn/x86_64/amd64/mul_basecase.as D mpn/x86_64/amd64/add_n.as D mpn/x86_64/amd64/addmul_1.as D mpn/x86_64/amd64/sub_n.as D mpn/x86_64/amd64/submul_1.as D mpn/x86_64/amd64/README D mpn/x86_64/amd64/sqr_basecase.as U mpn/x86_64/amd64/gmp-mparam.h A mpn/x86_64/amd64/sumdiff_n.asm A mpn/x86_64/amd64/lshift1.asm A mpn/x86_64/amd64/rshift1.asm A mpn/x86_64/amd64/nior_n.asm A mpn/x86_64/amd64/iorn_n.asm A mpn/x86_64/amd64/submul_1.asm A mpn/x86_64/amd64/lshift.asm A mpn/x86_64/amd64/com_n.asm A mpn/x86_64/amd64/nand_n.asm A mpn/x86_64/amd64/addlsh1_n.asm A mpn/x86_64/amd64/sublsh1_n.asm A mpn/x86_64/amd64/divebyff.asm A mpn/x86_64/amd64/rshift.asm A mpn/x86_64/amd64/redc_basecase.asm A mpn/x86_64/amd64/xnor_n.asm A mpn/x86_64/amd64/add_n.asm A mpn/x86_64/amd64/diveby3.asm A mpn/x86_64/amd64/sub_n.asm A mpn/x86_64/amd64/ior_n.asm A mpn/x86_64/amd64/k10 A mpn/x86_64/amd64/k10/gmp-mparam.h A mpn/x86_64/amd64/k10/popcount.asm A mpn/x86_64/amd64/k10/hamdist.asm A mpn/x86_64/amd64/k10/lshift.asm A mpn/x86_64/amd64/k10/rshift.asm A mpn/x86_64/amd64/mul_1.asm A mpn/x86_64/amd64/addadd_n.asm A mpn/x86_64/amd64/addsub_n.asm A mpn/x86_64/amd64/and_n.asm A mpn/x86_64/amd64/mul_basecase.asm A mpn/x86_64/amd64/xor_n.asm A mpn/x86_64/amd64/addmul_1.asm A mpn/x86_64/amd64/sqr_basecase.asm A mpn/x86_64/amd64/andn_n.asm U mpn/Makefile.am D mpn/generic/addsub_n.c A mpn/generic/sumdiff_n.c A mpn/generic/divebyff.c U mpn/generic/diveby3.c U mpn/generic/mul_fft.c U mpn/generic/bgcd.c U mpn/generic/sqrtrem.c A mpn/generic/redc_basecase.c U mpn/generic/mul_n.c U mpn/generic/sqr_basecase.c U mpn/asm-defs.m4 C build.vc9/lib_mpir_amd64/lib_mpir_amd64.vcproj C build.vc9/lib_mpir_p0/lib_mpir_p0.vcproj C build.vc9/dll_mpir_amd64/dll_mpir_amd64.vcproj C build.vc9/lib_mpir_p3/lib_mpir_p3.vcproj C build.vc9/lib_mpir_p4/lib_mpir_p4.vcproj C build.vc9/mpir-tests.sln C build.vc9/lib_mpir_gc/lib_mpir_gc.vcproj C build.vc9/mpir-tests/cxx.ostream.vcproj C build.vc9/mpir-tests/cxx.headers.vcproj C build.vc9/mpir-tests/cxx.istream.vcproj C build.vc9/mpir-tests/cxx.assign.vcproj C build.vc9/mpir-tests/cxx.prec.vcproj C build.vc9/mpir-tests/cxx.locale.vcproj C build.vc9/mpir-tests/cxx.constr.vcproj C build.vc9/mpir-tests/cxx.ternary.vcproj C build.vc9/mpir-tests/cxx.binary.vcproj C build.vc9/mpir-tests/cxx.misc.vcproj C build.vc9/mpir-tests/cxx.unary.vcproj C build.vc9/mpir-tests/cxx.ops.vcproj C build.vc9/mpir-tests/cxx.rand.vcproj C build.vc9/mpir-tests/cxx.cast.vcproj U build.vc9/config.amd64 C build.vc9/lib_mpir_core2/lib_mpir_core2.vcproj A build.vc9/g2y.py C build.vc9/dll_mpir_core2/dll_mpir_core2.vcproj C build.vc9/dll_mpir_p0/dll_mpir_p0.vcproj U build.vc9/mpir.sln C build.vc9/dll_mpir_p3/dll_mpir_p3.vcproj C build.vc9/dll_mpir_p4/dll_mpir_p4.vcproj C build.vc9/dll_mpir_gc/dll_mpir_gc.vcproj U mpz/powm.c U mpz/lucnum2_ui.c U mpz/lucnum_ui.c U mpz/fib_ui.c C demos/Makefile.in C demos/expr/Makefile.in U config.in U configure.in U compat.c U gmp-impl.h U yasm/yasm_parsers.7 U tune/speed.c U tune/speed.h U tune/common.c U tune/many.pl C configure C config.guess C tests/Makefile.in C tests/mpf/Makefile.in A tests/mpn/t-lorrshift1.c A tests/mpn/t-divebyff.c C tests/mpn/Makefile.in A tests/mpn/t-redc_basecase.c A tests/mpn/t-addadd_n.c A tests/mpn/t-addsub_n.c U tests/mpn/Makefile.am C tests/mpq/Makefile.in U tests/devel/try.c C tests/devel/Makefile.in C tests/cxx/Makefile.in C tests/mpz/Makefile.in U tests/refmpn.c C tests/rand/Makefile.in U tests/tests.h C tests/misc/Makefile.in U gmp-h.in A TODO --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
