1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
/* See LICENSE file for copyright and license details. */
#include "internals"
#define u libzahl_tmp_gcd_u
#define v libzahl_tmp_gcd_v
void
zgcd(z_t a, z_t b, z_t c)
{
/*
* Binary GCD algorithm.
*/
size_t shifts = 0, i = 0, min;
zahl_char_t uv, bit;
int neg;
if (!zcmp(b, c)) {
if (a != b)
zset(a, b);
return;
}
if (zzero(b)) {
if (a != c)
zset(a, c);
return;
}
if (zzero(c)) {
if (a != b)
zset(a, b);
return;
}
zabs(u, b);
zabs(v, c);
neg = zsignum(b) < 0 && zsignum(c) < 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);
zrsh(u, u, zlsb(u));
do {
zrsh(v, v, zlsb(v));
if (zcmpmag(u, v) > 0) /* Both are non-negative. */
zswap(u, v);
zsub_unsigned(v, v, u);
} while (!zzero(v));
zlsh(a, u, shifts);
SET_SIGNUM(a, neg ? -1 : 1);
}
|
