| 908 | // ------------------------------------------------ |
| 909 | |
| 910 | void Int::GCD(Int *a) { |
| 911 | |
| 912 | uint32_t k; |
| 913 | uint32_t b; |
| 914 | |
| 915 | Int U(this); |
| 916 | Int V(a); |
| 917 | Int T; |
| 918 | |
| 919 | if(U.IsZero()) { |
| 920 | Set(&V); |
| 921 | return; |
| 922 | } |
| 923 | |
| 924 | if(V.IsZero()) { |
| 925 | Set(&U); |
| 926 | return; |
| 927 | } |
| 928 | |
| 929 | if(U.IsNegative()) U.Neg(); |
| 930 | if(V.IsNegative()) V.Neg(); |
| 931 | |
| 932 | k = 0; |
| 933 | while (U.GetBit(k)==0 && V.GetBit(k)==0) |
| 934 | k++; |
| 935 | U.ShiftR(k); |
| 936 | V.ShiftR(k); |
| 937 | if (U.GetBit(0)==1) { |
| 938 | T.Set(&V); |
| 939 | T.Neg(); |
| 940 | } else { |
| 941 | T.Set(&U); |
| 942 | } |
| 943 | |
| 944 | do { |
| 945 | |
| 946 | if( T.IsNegative() ) { |
| 947 | T.Neg(); |
| 948 | b=0;while(T.GetBit(b)==0) b++; |
| 949 | T.ShiftR(b); |
| 950 | V.Set(&T); |
| 951 | T.Set(&U); |
| 952 | } else { |
| 953 | b=0;while(T.GetBit(b)==0) b++; |
| 954 | T.ShiftR(b); |
| 955 | U.Set(&T); |
| 956 | } |
| 957 | |
| 958 | T.Sub(&V); |
| 959 | |
| 960 | } while (!T.IsZero()); |
| 961 | |
| 962 | // Store gcd |
| 963 | Set(&U); |
| 964 | ShiftL(k); |
| 965 | |
| 966 | } |
| 967 |