From 2ce357e830db90b9a431362c66bdcf00e05e651e Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Wed, 2 Mar 2016 21:21:11 +0100 Subject: zgcd: optimisation of the first loop MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/zgcd.c | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'src/zgcd.c') diff --git a/src/zgcd.c b/src/zgcd.c index 91216ac..7e65ebf 100644 --- a/src/zgcd.c +++ b/src/zgcd.c @@ -12,7 +12,7 @@ zgcd(z_t a, z_t b, z_t c) * Binary GCD algorithm. */ - size_t shifts = 0, i = 0; + size_t shifts = 0, i = 0, min; zahl_char_t uv, bit; int neg; @@ -36,13 +36,21 @@ zgcd(z_t a, z_t b, z_t c) zabs(v, c); neg = zsignum(b) < 0 && zsignum(c) < 0; - for (;; i++) { - uv = (i < u->used ? u->chars[i] : 0) - | (i < v->used ? v->chars[i] : 0); + min = u->used < v->used ? u->used : v->used; + for (; i < min; i++) { + uv = u->chars[i] | v->used[i]; for (bit = 1; bit; bit <<= 1, shifts++) if (uv & bit) goto loop_done; } + for (; i < u->used; i++) + for (bit = 1; bit; bit <<= 1, shifts++) + if (u->chars[i] & bit) + goto loop_done; + for (; i < v->used; i++) + for (bit = 1; bit; bit <<= 1, shifts++) + if (v->chars[i] & bit) + goto loop_done; loop_done: zrsh(u, u, shifts); zrsh(v, v, shifts); -- cgit v1.2.3-70-g09d2