7 #include "cln/integer.h"
14 // Liefert den ggT zweier Integers.
16 // > a,b: zwei Integers
17 // < ergebnis: (gcd a b), ein Integer >=0
18 uint32 gcd (uint32 a, uint32 b)
23 // (when (oddp a) (if (oddp b) (go 2) (go 4)))
24 // (when (oddp b) (go 3))
25 // (incf j) (setq a (/ a 2)) (setq b (/ b 2))
27 // 2 {a,b >0, beide ungerade}
28 // (cond ((> a b) (setq a (- a b)) (go 3))
30 // ((< a b) (setq b (- b a)) (go 4))
32 // 3 {a,b >0, a gerade, b ungerade}
33 // (repeat (setq a (/ a 2)) (until (oddp a)))
35 // 4 {a,b >0, a ungerade, b gerade}
36 // (repeat (setq b (/ b 2)) (until (oddp b)))
41 // Statt j zu erhöhen und immer Bit 0 von a und b abfragen,
42 // fragen wir stattdessen immer Bit j von a und b ab; Bits j-1..0 sind =0.
44 #ifdef DUMMER_GGT // so macht's ein Mathematiker:
45 if (a==0) { return b; }
46 if (b==0) { return a; }
47 var uint32 bit_j = bit(0);
50 if (!((a & bit_j) ==0))
51 { if (!((b & bit_j) ==0)) goto odd_odd; else goto odd_even; }
52 if (!((b & bit_j) ==0)) goto even_odd;
56 #else // Trick von B. Degel:
57 var uint32 bit_j = (a | b); // endet mit einer 1 und j Nullen
58 bit_j = bit_j ^ (bit_j - 1); // Maske = bit(j) | bit(j-1) | ... | bit(0)
59 if (!((a & bit_j) ==0))
60 { if (!((b & bit_j) ==0))
68 if (!((b & bit_j) ==0))
74 return 0; // a=b=0 -> Ergebnis 0
77 { odd_odd: // a,b >0, beide ungerade
78 // Vergleiche a und b:
79 if (a == b) break; // a=b>0 -> fertig
82 even_odd: // a,b >0, a gerade, b ungerade
83 do { a = a>>1; } while ((a & bit_j) ==0);
87 odd_even: // a,b >0, a ungerade, b gerade
88 do { b = b>>1; } while ((b & bit_j) ==0);