A typescript implementation of the gcd and Extended Euclidean algorithm.
-
gcd: The Greatest Common Divisor.
-
Extended Euclidean algorithm: For solving the smallest integer solution (|x| + |y| smallest) of the equation
Ax + By = gcd(x,y)
.
-
npm
npm install --save @algorithm.ts/gcd
-
yarn
yarn add @algorithm.ts/gcd
-
gcd
import { gcd, gcdBigint } from '@algorithm.ts/gcd' gcd(3, 4) // => 1 gcdBigint(3n, 6n) // => 3n
-
Extended Euclidean algorithm
import { euclidean, euclideanBigint } from '@algorithm.ts/gcd' // 3x + 4y = gcd(3, 4) euclidean(3, 4) // => [-1, 1, 1] euclidean(3, 8) // => [3, -1, 1] euclideanBigint(6, 8) // => [-1n, 1n, 2n]