implementing euclid 27s extended algorithm

1def extendEuclidean(a, b, s1=1, s2=0, t1=0, t2=1):
2    
3    if b:
4        r=a%b
5        return extendEuclidean(b, r, s2, s1-s2*(a//b), t2, t1-t2*(a//b))
6    
7    return a, s1, t1

1int gcd(int a, int b, int& x, int& y) {
2    if (b == 0) {
3        x = 1;
4        y = 0;
5        return a;
6    }
7    int x1, y1;
8    int d = gcd(b, a % b, x1, y1);
9    x = y1;
10    y = x1 - y1 * (a / b);
11    return d;
12}
13

1.wp-block-code {
2	border: 0;
3	padding: 0;
4}
5
6.wp-block-code > div {
7	overflow: auto;
8}
9
10.shcb-language {
11	border: 0;
12	clip: rect(1px, 1px, 1px, 1px);
13	-webkit-clip-path: inset(50%);
14	clip-path: inset(50%);
15	height: 1px;
16	margin: -1px;
17	overflow: hidden;
18	padding: 0;
19	position: absolute;
20	width: 1px;
21	word-wrap: normal;
22	word-break: normal;
23}
24
25.hljs {
26	box-sizing: border-box;
27}
28
29.hljs.shcb-code-table {
30	display: table;
31	width: 100%;
32}
33
34.hljs.shcb-code-table > .shcb-loc {
35	color: inherit;
36	display: table-row;
37	width: 100%;
38}
39
40.hljs.shcb-code-table .shcb-loc > span {
41	display: table-cell;
42}
43
44.wp-block-code code.hljs:not(.shcb-wrap-lines) {
45	white-space: pre;
46}
47
48.wp-block-code code.hljs.shcb-wrap-lines {
49	white-space: pre-wrap;
50}
51
52.hljs.shcb-line-numbers {
53	border-spacing: 0;
54	counter-reset: line;
55}
56
57.hljs.shcb-line-numbers > .shcb-loc {
58	counter-increment: line;
59}
60
61.hljs.shcb-line-numbers .shcb-loc > span {
62	padding-left: 0.75em;
63}
64
65.hljs.shcb-line-numbers .shcb-loc::before {
66	border-right: 1px solid #ddd;
67	content: counter(line);
68	display: table-cell;
69	padding: 0 0.75em;
70	text-align: right;
71	-webkit-user-select: none;
72	-moz-user-select: none;
73	-ms-user-select: none;
74	user-select: none;
75	white-space: nowrap;
76	width: 1%;
77}
78int exeuclid(int a, int m)
79{
80     int A3 = m;
81     int A2 = 0, A1 = 1;
82
83     if (m == 1)
84          return 0;
85
86     while (a > 1)
87     {
88          // q is quotient
89          int q = a / m;
90
91          int t = m;
92
93          // m is remainder now, process
94          // same as Euclid's algo
95          m = a % m;
96          a = t;
97          t = A2;
98
99          // Update A1 and A2
100          A2 = A1 - q * A2;
101          A1 = t;
102      }
103
104     // Make A1 positive
105     if (A1 < 0)
106     A1 += A3;
107     return A1;
108}Code language: JavaScript (javascript)

1import java.util.Scanner;
2class Lab3{
3     //euclids algorithm
4     int euclid(int a, int b){
5          if(b==0)
6               return a;
7          else
8               return euclid(b, a%b);
9          }
10     //euclids extended algorithm
11     int exeuclid(int a, int m)
12     {
13          int A3 = m;
14          int A2 = 0, A1 = 1;
15          if (m == 1)
16               return 0;
17
18          while (a > 1)
19          {
20               // q is quotient
21               int q = a / m;
22
23               int t = m;
24
25               // m is remainder now, process
26               // same as Euclid's algo
27               m = a % m;
28               a = t;
29               t = A2;
30
31               // Update A1 and A2
32               A2 = A1 - q * A2;
33               A1 = t;
34          }
35
36          // Make A1 positive
37          if (A1 < 0)
38          A1 += A3;
39          return A1;
40     }
41     public static void main(String[] args) {
42          Lab3 ob = new Lab3();
43          int x, y, choice;
44
45          Scanner input = new Scanner(System.in);
46          System.out.println("Enter Choice \n Enter 1 for gcd and 2 for extended ed");
47          choice=input.nextInt();
48          switch(choice)
49          {
50               case 1:
51                    int output;
52                    System.out.println("Enter the first number");
53                    x = input.nextInt();
54                    System.out.println("Enter the second number");
55                    y = input.nextInt();
56                    output = ob.euclid(x, y);
57                    System.out.println("GCD is:"+output);
58                    break;
59               case 2:
60                    System.out.println("To Find Inverse");
61                    int m, b;
62                    System.out.println("Enter m");
63                    m=input.nextInt();
64                    System.out.println("Enter b");
65                    b = input.nextInt();
66                    System.out.println("Inverse is equal to: "+ob.exeuclid(m, b));
67                    break;
68               default:
69                    System.out.println("Wrong Choice");
70          }
71
72     }
73}Code language: JavaScript (javascript)