[Gmp-commit] /var/hg/gmp: Added comment to explain the mod_1_1 algorithm.

mercurial at gmplib.org mercurial at gmplib.org
Tue Feb 22 20:43:52 CET 2011

details:   /var/hg/gmp/rev/f705ef6c2c10
changeset: 13885:f705ef6c2c10
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Tue Feb 22 20:43:22 2011 +0100
Added comment to explain the mod_1_1 algorithm.


 mpn/x86_64/mod_1_1.asm |  19 +++++++++++++++++++
 1 files changed, 19 insertions(+), 0 deletions(-)

diffs (29 lines):

diff -r 9c6ea89eed2c -r f705ef6c2c10 mpn/x86_64/mod_1_1.asm
--- a/mpn/x86_64/mod_1_1.asm	Tue Feb 22 18:47:08 2011 +0100
+++ b/mpn/x86_64/mod_1_1.asm	Tue Feb 22 20:43:22 2011 +0100
@@ -53,6 +53,25 @@
 C by caller.  Perhaps b shouldn't be passed at all, it should be in the pre
 C block where the cps function is free to store whatever is needed.
+C The iteration is almost as follows,
+C   r_2 B^3 + r_1 B^2 + r_0 B + u = r_1 B2modb + (r_0 + r_2 B2mod) B + u
+C where r2 is a single bit represented as a mask. But to make sure that the
+C result fits in two limbs and a bit, carry from the addition
+C   r_0 + r_2 B2mod
+C is handled specially. On carry, we subtract b to cancel the carry,
+C and we use instead the value
+C   r_0 + B2mb (mod B)
+C This addition can be issued early since it doesn't depend on r2, and it is
+C the source of the cmov in the loop.
+C We have the invariant that r_2 B^2 + r_1 B + r_0 < B^2 + B b

More information about the gmp-commit mailing list