[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
description:
Added comment to explain the mod_1_1 algorithm.
diffstat:
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
+C r_2 B^3 + r_1 B^2 + r_0 B + u = r_1 B2modb + (r_0 + r_2 B2mod) B + u
+C
+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
+C r_0 + r_2 B2mod
+C
+C is handled specially. On carry, we subtract b to cancel the carry,
+C and we use instead the value
+C
+C r_0 + B2mb (mod B)
+C
+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
+C We have the invariant that r_2 B^2 + r_1 B + r_0 < B^2 + B b
+
ASM_START()
TEXT
ALIGN(16)
More information about the gmp-commit
mailing list