JavaScript calculation with all steps of the ggt/gdc (größter gemeinsamer Teiler/greatest common divisor) with the (extended) euclidean algorithm. Quick script to double check hand calculations for 'simultane Kongruenzen', RSA, ...

extendedEuclideanAlgorithm.js

#!/usr/bin/env node
'use strict'

/*
 * This file contains:
 * Methods to run the euclidean algorithm and the extended euclidean algorithm
 * and methods to print the calculation steps visually to the console
 *
 * RUN:
 * - node: enter in the console 'node extendedEuclideanAlgorithm.js'
 * - browser: Open console and insert the whole document from line 16 to finish and press enter
 */

const {performance} = require('perf_hooks')

/**
 * Calculate the ggt with the euclidean algorithm
 * @param {number} numberOne the first number
 * @param {number} numberTwo the second number
 * @param {number[][]} steps calculation steps of the euclidean algorithm
 * @returns {{ggt: number, calculation: number[][]}}
 */
function euclideanAlgorithm (numberOne, numberTwo, steps = []) {
  // If the numbers are the same terminate with this number
  if (numberOne === numberTwo) {
    steps.push([numberOne, 1, numberTwo, 0])
    return {ggt: numberOne, calculation: steps}
  }
  // If the second number is bigger than the first swap them
  if (numberTwo > numberOne) {
    steps.push([numberOne, numberTwo])
    return euclideanAlgorithm(numberTwo, numberOne, steps)
  }
  // Otherwise execute the algorithm
  const rest = numberOne % numberTwo
  steps.push([numberOne, (numberOne - rest) / numberTwo, numberTwo, rest])
  // If the rest is zero terminate else continue recursively
  return rest === 0 ? {ggt: numberTwo, calculation: steps} : euclideanAlgorithm(numberTwo, rest, steps)
}

/**
 * Calculate the ggt with the extended euclidean algorithm
 * @param {number} numberOne the first number
 * @param {number} numberTwo the second number
 * @param {number} ggt greatest common divisor
 * @param {number[][]} ggtSteps calculation steps of the euclidean algorithm
 * @param {number[][]} backwardsSteps calculation steps of the extended euclidean algorithm
 * @returns {{ggt: number, x: number, y: number, calculationEuclidean: number[][], calculationExtendedEuclidean: number[][]}}
 */
function extendedEuclideanAlgorithm (numberOne, numberTwo, ggt = -1, ggtSteps = [], backwardsSteps = []) {
  // Check if the ggt needs to be calculated with the euclidean algorithm
  if (ggt === -1) {
    const result = euclideanAlgorithm(numberOne, numberTwo)
    return extendedEuclideanAlgorithm(numberOne, numberTwo, result.ggt, result.calculation)
  }
  // Otherwise execute the algorithm
  for (let i = ggtSteps.length - 2; i >= 0; i--) {
    const element = ggtSteps[i]
    // If index is the second last line start with the following values initialize algorithm
    if (i === ggtSteps.length - 2) {
      backwardsSteps.push([element[3], 1, element[0], (-element[1]), element[2]])
    } else {
      // Otherwise substitute from the last line the last number with the current line
      const lastElement = backwardsSteps[backwardsSteps.length - 1]
      backwardsSteps.push([lastElement[0], lastElement[3], element[0], (lastElement[3] * -element[1]) + lastElement[1], element[2]])
    }
  }
  const lastBackwardsStep = backwardsSteps[backwardsSteps.length - 1]
  return {ggt: ggt, x: lastBackwardsStep[1], y: lastBackwardsStep[3], calculationEuclidean: ggtSteps, calculationExtendedEuclidean: backwardsSteps}
}

/**
 * Add leading/trailing whitespaces to the string representation of an object
 * @param {*} x the object that should get leading/trailing whitespaces
 * @param {number} length how long should the string at least be
 * @param {boolean} front add leading whitespaces (or trailing if false)
 * @returns {string} string in the correct length (or longer if length was smaller than x)
 */
function formatLength (x, length, front = true) {
  // Check if the string representation of the object is already long enough / longer
  const missingLength = length - ('' + x).length
  if (missingLength <= 0) {
    return '' + x
  } else {
    // If not add the missing length in front of the number
    return front ? ' '.repeat(missingLength) + x : x + ' '.repeat(missingLength)
  }
}

/**
 * Get which object has a longer string representation
 * @param {*} x object one
 * @param {*} y object two
 * @returns {*} the object with the longer string representation
 */
function getLongerStringRepresentation (x, y) {
  // Check if the string representation length of object x is greater or the same as the object y
  return ('' + x).length >= ('' + y).length ? x : y
}

/**
 * Graphical output of the euclidean algorithm between two numbers
 * @param {number} numberOne
 * @param {number} numberTwo
 */
function outputCalculationEuclideanAlgorithm (numberOne, numberTwo) {
  // Do the calculation
  const t0 = performance.now()
  const result = euclideanAlgorithm(numberOne, numberTwo)
  const t1 = performance.now()
  console.log('Calculation [euclidean algorithm] took ' + (t1 - t0) + ' milliseconds.')
  // Output calculation [euclidean algorithm]
  console.log('CALCULATION: [euclidean algorithm]')
  // Get the longest parameter for each output for visual alignment
  let maximums = new Array(result.calculation[result.calculation.length - 1].length + 1).fill(0)
  let prevCounter = 0
  for (let i = 0; i < result.calculation.length; i++) {
    const element = result.calculation[i]
    if (element.length !== 2) {
      maximums[element.length] = ('' + (++prevCounter)).length
      for (let j = 0; j < element.length; j++) {
        maximums[j] = getLongerStringRepresentation(maximums[j], element[j])
      }
    }
  }
  for (let i = 0; i < maximums.length; i++) {
    maximums[i] = ('' + maximums[i]).length
  }
  // Output each calculation step
  let steps = 0
  for (let index = 0; index < result.calculation.length; index++) {
    const element = result.calculation[index]
    if (index === 0 && element.length === 2) {
      // Indicate that the values were swapped
      console.log(element[0] + ' < ' + element[1] + ' -> Swap them')
    } else {
      // When this is not the last step display a number for each step
      const stepString = index === result.calculation.length - 1
        ? ' '.repeat(('' + formatLength(++steps, maximums[maximums.length - 1] + 2)).length)
        : '(' + formatLength(++steps, maximums[maximums.length - 1]) + ')'
        // Display calculation step
      console.log(stepString + ' ' + formatLength(element[0], maximums[0]) + ' = ' + formatLength(element[1], maximums[1]) + ' * ' + formatLength(element[2], maximums[2]) + ' + ' + formatLength(element[3], maximums[3]))
    }
  }
  // Output all results
  console.log('RESULT:')
  console.log('>> ggT(' + numberOne + ',' + numberTwo + ') = ' + result.ggt)
}

/**
 * Graphical output of the extended euclidean algorithm between two numbers
 * @param {number} numberOne
 * @param {number} numberTwo
 */
function outputCalculationoutputCalculationExtendedEuclideanAlgorithm (numberOne, numberTwo) {
  // Do the calculation
  const t0 = performance.now()
  const result = extendedEuclideanAlgorithm(numberOne, numberTwo)
  const t1 = performance.now()
  console.log('Calculation [extended euclidean algorithm] took ' + (t1 - t0) + ' milliseconds.')
  // Output calculation [euclidean algorithm]
  outputCalculationEuclideanAlgorithm(numberOne, numberTwo)
  // Output calculation [extended euclidean algorithm]
  console.log('CALCULATION: [extended euclidean algorithm]')
  let maximums = new Array(result.calculationExtendedEuclidean[result.calculationExtendedEuclidean.length - 1].length + 1).fill(0)
  let counter = result.calculationExtendedEuclidean[0].length === 2 ? result.calculationExtendedEuclidean.length - 1 : result.calculationExtendedEuclidean.length
  for (let i = 0; i < result.calculationExtendedEuclidean.length; i++) {
    const element = result.calculationExtendedEuclidean[i]
    for (let j = 0; j < element.length; j++) {
      maximums[j] = getLongerStringRepresentation(maximums[j], element[j])
    }
  }
  maximums[result.calculationExtendedEuclidean[result.calculationExtendedEuclidean.length - 1].length] = ('' + counter).length
  for (let i = 0; i < maximums.length; i++) {
    maximums[i] = ('' + maximums[i]).length
  }
  for (let i = 0; i < result.calculationExtendedEuclidean.length; i++) {
    const element = result.calculationExtendedEuclidean[i]
    if (i === 0) {
      // Initial step
      console.log('Initial Step: ' + formatLength(element[0], maximums[3], false) + ' = ' + formatLength(element[1], maximums[1]) + 'x' + formatLength(element[2], maximums[2]) + ' + ' + formatLength(element[3], maximums[3]) + 'x' + formatLength(element[4], maximums[4]) + ' ' + formatLength('(' + counter + ')', maximums[5] + 2))
    } else {
      // substitute step
      const lastElement = result.calculationExtendedEuclidean[i - 1]
      console.log(formatLength('Substitute ' + lastElement[4] + ': ', ('Initial Step: ' + formatLength(element[0], maximums[3], false)).length, false) + ' = ' + formatLength(element[1], maximums[1]) + 'x' + formatLength(element[2], maximums[2]) + ' + ' + formatLength(element[3], maximums[3]) + 'x' + formatLength(element[4], maximums[4]) + ' ' + formatLength('(' + counter + ')', maximums[5] + 2))
    }
    counter--
  }
  // Output all results
  console.log('RESULT:')
  const biggerNumber = numberOne > numberTwo ? numberOne : numberTwo
  const smallerNumber = numberOne <= numberTwo ? numberOne : numberTwo
  console.log('>> ' + result.x + 'x' + biggerNumber + ' + ' + result.y + 'x' + smallerNumber + ' = ' + result.ggt)
}

// test
const t0 = performance.now()
outputCalculationoutputCalculationExtendedEuclideanAlgorithm(6950619, 405769)
const t1 = performance.now()
console.log('Printing + Calculation took ' + (t1 - t0) + ' milliseconds.')