egcd top-level property

dynamic egcd

Extended Euclidean algorithm.

Returns a list of lists where each sublist contains [d, x, y] for each pair.

Example:

print(egcd(48, 18, 24));  // Output: [[6, -1, 3], [6, -1, 1]]

Implementation

dynamic egcd = VarArgsFunction((args, kwargs) {
  List<num> numbers = _getArgsParams(args);

  List<List<Complex>> results = [];

  // Helper function to compute egcd for a pair of numbers
  List<Complex> egcdPair(num a, num b) {
    num x = 1, y = 0, x1 = 0, y1 = 1;
    while (b != 0) {
      num q = a ~/ b;
      num r = mod(a, b); // Modulo operation using custom function
      num x2 = x - q * x1;
      num y2 = y - q * y1;
      x = x1;
      y = y1;
      x1 = x2;
      y1 = y2;
      a = b;
      b = r;
    }
    return [Complex(a), Complex(x), Complex(y)];
  }

  // Iterate through pairs of numbers and compute egcd using the iterative function
  for (int i = 0; i < numbers.length - 1; i++) {
    results.add(egcdPair(numbers[i], numbers[i + 1]));
  }

  return results;
});