如何在 GNU Octave / Matlab 中计算向量的 GCD

Question

gcd (A1, A2, ...) 计算元素 A1(1), A2(1), ... 的 GCD。作为存储在向量A中的元素，如何计算gcd (A)？
（我的意思是，gcd (4, 2, 8) = 2、gcd ([4, 2, 8] 会在 GNU Octave 4.0.0 中引发错误）。

Answer 1

以下是粗略的，但似乎适用于简单的示例

function g = gcd_array(vals)
if length(vals) == 1
    g = vals;
else
    g = gcd(vals(1), gcd_array(vals(2:end)));
endif

Answer 2

请注意，与 Octave 不同，Matlab gcd 函数只需要两个输入参数。由于 gcd(a,b,c) = gcd(a,gcd(b,c)) 的事实，您可以使用递归来处理它。以下函数接受两种输入格式——单个向量或多个标量输入，并且应该在 Matlab 和 Octave 中都有效：

function divisor = gcd_vect(a, varargin)
    if ~isempty(varargin)
        a = [a, varargin{:}];
    elseif length(a) == 1
        divisor = a;
        return;
    end
    divisor = gcd(a(1), gcd_vect(a(2:end)));
end

Answer 3

有元胞数组扩展

这里是一行代码，仅在八度音程中有效（感谢 nirvana-msu 指出了 matlab 的局限性）：

A = [10 25 15];
gcd(num2cell(A){:})
# ans =  5

这里使用元胞数组扩展，有点隐藏there :

Accessing multiple elements of a cell array with the ‘{’ and ‘}’ operators will result in a comma separated list of all the requested elements

所以这里 A{:} 被解释为 A(1), A(2), A(3)，因此 gcd(A{:}) 被解释为 gcd(A(1), A(2), A(3))

性能

还在八度以下

A = 3:259;
tic; gcd(num2cell(A){:}); toc

Elapsed time is 0.000228882 seconds.

@nirvana_msu 回答中的 gcd_vect，

tic; gcd_vect(A); toc

Elapsed time is 0.0184669 seconds.

这是因为使用递归意味着高性能损失（至少在八度以下）。而实际上对于A中超过256个元素，递归限制已经用尽

tic; gcd_vect(1:257); toc

<... snipped bunch of errors as ...>
error: evaluating argument list element number 2
error: called from
gcd_vect at line 8 column 13

这可以通过使用 Divide and conquer algorithm

得到很大改善

虽然元胞数组扩展（仅八度音阶）扩展良好：

A = 127:100000;
tic; gcd(num2cell(A){:}); toc
Elapsed time is 0.0537438 seconds.

分而治之算法（最佳）

这个应该也可以在 matlab 下工作（虽然没有测试。欢迎反馈）。

它也使用递归，就像在其他答案中一样，但是 Divide and conquer

function g = gcd_array(A)
  N = numel(A);

  if (mod(N, 2) == 0)
    % even number of elements
    % separate in two parts of equal length
    idx_cut = N / 2;
    part1 = A(1:idx_cut);
    part2 = A(idx_cut+1:end);
    % use standard gcd to compute gcd of pairs
    g = gcd(part1(:), part2(:));
    if ~ isscalar(g)
       % the result was an array, compute its gcd
       g = gcd_array(g);
    endif
  else
    % odd number of elements
    % separate in one scalar and an array with even number of elements
    g = gcd(A(1), gcd_array(A(2:end)));
  endif
endfunction

时间：

A = 127:100000;
tic; gcd_array(A); toc
Elapsed time is 0.0184278 seconds.

所以这似乎比元胞数组扩展更好。

如何在 GNU Octave / Matlab 中计算向量的 GCD

How to compute the GCD of a vector in GNU Octave / Matlab

matlab

octave

greatest-common-divisor

有元胞数组扩展

性能

分而治之算法（最佳）