Answers for "euclid's extended algorithm"

extended euclidean algorithm

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

extended euclidean algorithm

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

implementing euclid's extended algorithm

import java.util.Scanner;
class Lab3{
     //euclids algorithm
     int euclid(int a, int b){
          if(b==0)
               return a;
          else
               return euclid(b, a%b);
          }
     //euclids extended algorithm
     int exeuclid(int a, int m)
     {
          int A3 = m;
          int A2 = 0, A1 = 1;
          if (m == 1)
               return 0;

          while (a > 1)
          {
               // q is quotient
               int q = a / m;

               int t = m;

               // m is remainder now, process
               // same as Euclid's algo
               m = a % m;
               a = t;
               t = A2;

               // Update A1 and A2
               A2 = A1 - q * A2;
               A1 = t;
          }

          // Make A1 positive
          if (A1 < 0)
          A1 += A3;
          return A1;
     }
     public static void main(String[] args) {
          Lab3 ob = new Lab3();
          int x, y, choice;

          Scanner input = new Scanner(System.in);
          System.out.println("Enter Choice \n Enter 1 for gcd and 2 for extended ed");
          choice=input.nextInt();
          switch(choice)
          {
               case 1:
                    int output;
                    System.out.println("Enter the first number");
                    x = input.nextInt();
                    System.out.println("Enter the second number");
                    y = input.nextInt();
                    output = ob.euclid(x, y);
                    System.out.println("GCD is:"+output);
                    break;
               case 2:
                    System.out.println("To Find Inverse");
                    int m, b;
                    System.out.println("Enter m");
                    m=input.nextInt();
                    System.out.println("Enter b");
                    b = input.nextInt();
                    System.out.println("Inverse is equal to: "+ob.exeuclid(m, b));
                    break;
               default:
                    System.out.println("Wrong Choice");
          }

     }
}Code language: JavaScript (javascript)

implementing euclid's extended algorithm

import java.util.Scanner;
class Lab3{
     //euclids algorithm
     int euclid(int a, int b){
          if(b==0)
               return a;
          else
               return euclid(b, a%b);
          }
     //euclids extended algorithm
     int exeuclid(int a, int m)
     {
          int A3 = m;
          int A2 = 0, A1 = 1;
          if (m == 1)
               return 0;

          while (a > 1)
          {
               // q is quotient
               int q = a / m;

               int t = m;

               // m is remainder now, process
               // same as Euclid's algo
               m = a % m;
               a = t;
               t = A2;

               // Update A1 and A2
               A2 = A1 - q * A2;
               A1 = t;
          }

          // Make A1 positive
          if (A1 < 0)
          A1 += A3;
          return A1;
     }
     public static void main(String[] args) {
          Lab3 ob = new Lab3();
          int x, y, choice;

          Scanner input = new Scanner(System.in);
          System.out.println("Enter Choice \n Enter 1 for gcd and 2 for extended ed");
          choice=input.nextInt();
          switch(choice)
          {
               case 1:
                    int output;
                    System.out.println("Enter the first number");
                    x = input.nextInt();
                    System.out.println("Enter the second number");
                    y = input.nextInt();
                    output = ob.euclid(x, y);
                    System.out.println("GCD is:"+output);
                    break;
               case 2:
                    System.out.println("To Find Inverse");
                    int m, b;
                    System.out.println("Enter m");
                    m=input.nextInt();
                    System.out.println("Enter b");
                    b = input.nextInt();
                    System.out.println("Inverse is equal to: "+ob.exeuclid(m, b));
                    break;
               default:
                    System.out.println("Wrong Choice");
          }

     }
}Code language: JavaScript (javascript)

implementing euclid's extended algorithm

.wp-block-code {
	border: 0;
	padding: 0;
}

.wp-block-code > div {
	overflow: auto;
}

.shcb-language {
	border: 0;
	clip: rect(1px, 1px, 1px, 1px);
	-webkit-clip-path: inset(50%);
	clip-path: inset(50%);
	height: 1px;
	margin: -1px;
	overflow: hidden;
	padding: 0;
	position: absolute;
	width: 1px;
	word-wrap: normal;
	word-break: normal;
}

.hljs {
	box-sizing: border-box;
}

.hljs.shcb-code-table {
	display: table;
	width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
	color: inherit;
	display: table-row;
	width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
	display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
	white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
	white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
	border-spacing: 0;
	counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
	counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
	padding-left: 0.75em;
}

.hljs.shcb-line-numbers .shcb-loc::before {
	border-right: 1px solid #ddd;
	content: counter(line);
	display: table-cell;
	padding: 0 0.75em;
	text-align: right;
	-webkit-user-select: none;
	-moz-user-select: none;
	-ms-user-select: none;
	user-select: none;
	white-space: nowrap;
	width: 1%;
}
int exeuclid(int a, int m)
{
     int A3 = m;
     int A2 = 0, A1 = 1;

     if (m == 1)
          return 0;

     while (a > 1)
     {
          // q is quotient
          int q = a / m;

          int t = m;

          // m is remainder now, process
          // same as Euclid's algo
          m = a % m;
          a = t;
          t = A2;

          // Update A1 and A2
          A2 = A1 - q * A2;
          A1 = t;
      }

     // Make A1 positive
     if (A1 < 0)
     A1 += A3;
     return A1;
}Code language: JavaScript (javascript)

implementing euclid's extended algorithm

.wp-block-code {
	border: 0;
	padding: 0;
}

.wp-block-code > div {
	overflow: auto;
}

.shcb-language {
	border: 0;
	clip: rect(1px, 1px, 1px, 1px);
	-webkit-clip-path: inset(50%);
	clip-path: inset(50%);
	height: 1px;
	margin: -1px;
	overflow: hidden;
	padding: 0;
	position: absolute;
	width: 1px;
	word-wrap: normal;
	word-break: normal;
}

.hljs {
	box-sizing: border-box;
}

.hljs.shcb-code-table {
	display: table;
	width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
	color: inherit;
	display: table-row;
	width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
	display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
	white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
	white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
	border-spacing: 0;
	counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
	counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
	padding-left: 0.75em;
}

.hljs.shcb-line-numbers .shcb-loc::before {
	border-right: 1px solid #ddd;
	content: counter(line);
	display: table-cell;
	padding: 0 0.75em;
	text-align: right;
	-webkit-user-select: none;
	-moz-user-select: none;
	-ms-user-select: none;
	user-select: none;
	white-space: nowrap;
	width: 1%;
}
int exeuclid(int a, int m)
{
     int A3 = m;
     int A2 = 0, A1 = 1;

     if (m == 1)
          return 0;

     while (a > 1)
     {
          // q is quotient
          int q = a / m;

          int t = m;

          // m is remainder now, process
          // same as Euclid's algo
          m = a % m;
          a = t;
          t = A2;

          // Update A1 and A2
          A2 = A1 - q * A2;
          A1 = t;
      }

     // Make A1 positive
     if (A1 < 0)
     A1 += A3;
     return A1;
}Code language: JavaScript (javascript)