12 #include "cl_integer.h"
15 void partial_gcd (uintD z1, uintD z2, partial_gcd_result* erg)
22 // Hier ist z1-y1>=z2+y2.
23 // Bestimme q := floor((z1-y1)/(z2+y2)) >= 1 :
24 { var uintD zaehler = z1-y1;
25 var uintD nenner = z2+y2; // z2+y2 <= z1-y1 < beta !
26 if (floor(zaehler,8) >= nenner) // zaehler >= 8*nenner ?
27 // ja -> Dividieren lohnt sich wohl
28 { var uintD q = floorD(zaehler,nenner);
29 x1 += muluD_unchecked(q,x2); // x1 := x1+q*x2
30 y1 += muluD_unchecked(q,y2); // y1 := y1+q*y2
31 z1 -= muluD_unchecked(q,z2); // z1 := z1-q*z2
34 // nein -> ein paarmal subtrahieren ist wohl schneller
35 do { x1 += x2; y1 += y2; z1 -= z2; } // (x1,y1,z1) := (x1+x2,y1+y2,z1-z2)
36 while (z1-y1 >= nenner);
38 if (z2-x2 <= z1+x1-1) break;
39 // Hier ist z2-x2>=z1+x1.
40 // Bestimme q := floor((z2-x2)/(z1+x1)) >= 1 :
41 { var uintD zaehler = z2-x2;
42 var uintD nenner = z1+x1; // z1+x1 <= z2-x2 < beta !
43 if (floor(zaehler,8) >= nenner) // zaehler >= 8*nenner ?
44 // ja -> Dividieren lohnt sich wohl
45 { var uintD q = floorD(zaehler,nenner);
46 x2 += muluD_unchecked(q,x1); // x2 := x2+q*x1
47 y2 += muluD_unchecked(q,y1); // y2 := y2+q*y1
48 z2 -= muluD_unchecked(q,z1); // z2 := z2-q*z1
51 // nein -> ein paarmal subtrahieren ist wohl schneller
52 do { x2 += x1; y2 += y1; z2 -= z1; } // (x2,y2,z2) := (x2+x1,y2+y1,z2-z1)
53 while (z2-x2 >= nenner);
55 if (z1-y1 <= z2+y2-1) break;
57 // Keine Subtraktion mehr möglich.
58 erg->x1 = x1; erg->y1 = y1; erg->x2 = x2; erg->y2 = y2; // Ergebnis