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

[mercurial at gmplib.org]

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)