(old)Puppy Linux Discussion Forum

Code: Select all

#include<iostream>
#include<conio.h>
using namespace std;
typedef unsigned long ulong;


long eeuclid(long m, long b, long *inverse){        /// eeuclid( modulus, num whose inv is to be found, variable to put inverse )
    long A1 = 1, A2 = 0, A3 = m,
         B1 = 0, B2 = 1, B3 = b,
         T1, T2, T3, Q;

         cout<<endl<<"eeuclid() started"<<endl;

        while(1){
            if(B3 == 0){
                *inverse = 0;
                return A3;      // A3 = gcd(m,b)
            }

            if(B3 == 1){
                *inverse = B2; // B2 = b^-1 mod m
                return B3;      // A3 = gcd(m,b)
            }

            Q = A3/B3;

            T1 = A1 - Q*B1;
            T2 = A2 - Q*B2;
            T3 = A3 - Q*B3;

            A1 = B1; A2 = B2; A3 = B3;
            B1 = T1; B2 = T2; B3 = T3;
       }
    cout<<endl<<"ending eeuclid() "<<endl;
}

int main(){
    long a, b, c, d=0, e, inverse = 0;
    int ch;
        cout<<"Preparing extended Euclid ---> "<<endl;
        cout<<"m >> ";
        cin >> a;
        cout<<"b >> ";
        cin >> b;
        cout<<"gcd("<<a<<","<<b<<") = "<<eeuclid(a, b, &inverse);
        cout<<" and inverse  = "<<inverse<<endl;
        cout<<endl<<"Press q to quit ... "<<endl;
    return 0;
}

Code: Select all

cout<<"gcd("<<a<<","<<b<<") = "<<eeuclid(a, b, &inverse);
        cout<<" and inverse  = "<<inverse<<endl;

Code: Select all

cout<<"gcd("<<a<<","<<b<<") = "<<eeuclid(a, b, &inverse)<<" and inverse  = "<<inverse<<endl;