Euclid Algorithm

by evgkch

JavaScript

// НОД двух чисел
function gcd(a, b) {
	return b ? gcd(b, a % b) : a;
};

// НОД n-чисел
function gcds(...args) {
	return [...args].reduce(gcd);
};
// extended gcd
function xgcd(a, b) {
	let x, y;
  if (a === 0) return [b, 0, 1];
  const [g, x1, y1] = xgcd(b % a, a);
  x = y1 - Math.floor(b / a) * x1;
  y = x1;
  return [g, x, y];
}

console.log(xgcd(25, 120))

function createUnitVector(length, i = -1) {
	return Array.from({ length }, (v, k) => k === i ? 1 : 0);
}

const createMatrix = (...args) => {
  const argsLength = args.length;
  return Array.from({ length: argsLength }, (v, i) => [
    args[i],
    ...createUnitVector(argsLength, i)
  ]);
}

const doSortWithoutZeros = (i) => (a, b) => {
	if (!a[i]) return 1;
  else
  {
  	if (a[i] > b[i] && !b[i])
    	return 0;
    if (a[i] > b[i])
    	return 1;
    else
    	return -1;
  }
};

function xgcds(a, b, ...rest) {
	const result = [];
	return (c) => {
  	if (rest && rest.length > 0)
    	return xgcds(b, ...rest)(c);
    const g = xgcd(a, b);
    console.log(g)
  };
}

function _xgcds(...args) {
	const matrix = createMatrix(...args);
  const matrixRowLength = matrix.length;
  const matrixColLength = matrix[0].length;
	return (c) => {
  	const _A = [];
  	const A = f(matrix);
    /* const B = [-c, ...createUnitVector(matrixRowLength - 1)];
    for (let i = 0; i < matrixRowLength; i++)
    {
      B[i] = B[i] + c * A[0][i];
    }
    return [...A, B]; */
    return A;
    
  	function f(matrix) {
    	const m = matrix.sort(doSortWithoutZeros(0));
      // условие выхода
      if (m[1][0] === 0)
      	return m;
      const a = m[0][0];
      for (let i = 1; m[i] && m[i][0]; i++)
      {
      	// следующий элемент
      	const b = m[i][0];     
      	m[i][0] =  b % a;
        for (let j = 1; j < matrixColLength; j++)
        {
        	if (m[0][j])
          {
          	m[i][j] = m[i][j] - m[0][j] * Math.floor(b / a);
          }
        }
      };
      return f(m);
    };
    
  }
}

// console.log(xgcds(2,...